I saw a ‘simple’ puzzle on the internet which I thought I’d have a crack at in an evening. Several furious scribblings on the bus and the sofa later, I finally have an answer. I’m so relieved I can’t help but share the joy.
Uniformly draw a random real number between and . Repeat, drawing a number between and . You lose the game when you draw a number below . On average, how many turns do you last in the game?
I encourage you to have a go at this problem, and please let me know if you find a simple way to the answer. I’ll describe my method below. I didn’t know the answer beforehand, so likely didn’t take the most direct route to it.
The first turn
We draw the number with uniform probability, so the odds of picking a number in turn 1 between and is just
Simple. For illustration of this trivial example, I’ve plotted below the analytic solution for the probability density and a histogram of some numerical samples from a uniform distribution.
It’s obvious what the chance of losing in the first turn is, but I’ll be explicit to clarify the procedure. We need to integrate between and , or
One turn down, turns to go.
The second turn
Here it gets a little trickier. There is some chance that we lost the game in the first turn, so if we integrate the probability of picking a number in the second turn we should get a number less than unity.
Carrying on regardless, by the law of total probability and the fact that the values of we can pick are dependent on the previous that we picked,
The integration limits are very important here. The largest value that could take is . The smallest is , as remember we are picking a value such that .
From the first turn, , and similarly , so performing the integral
If we’ve made it to the second turn, it must have been that , and so the equation above is only valid for , as those values only receive contributions from the possibilities . There is obviously a chance that we can pick , but again these have only received contributions from the values . As passes down through , the probability can’t increase, and so stays constant from to .
This two-part distribution is plotted below, and as you can see agrees with some numerical tests.
Also, integrating ,
less than one as predicted, by an amount equal to the probability of losing in the first turn . The fact that it’s possible to lose the game is already priced in to these distributions, which will come in handy later.
The next turns
Armed with some insight on how to proceed, the distribution for the third turn is
This looks a bit nasty, but has a surprisingly pleasant solution
There’s looking to be a bit of a pattern here. Integrating by parts it’s possible to show the general solution for any turn (including the first one!)
Comparing this expression to numerical experiments, the agreement is very good:
Winning and losing
Armed with this expression, the original question can be answered. First of all, what’s the probability of winning turn ? Integrating the above from to ,
You will recognise the right-hand side as the first terms of the Taylor expansion of , so
and as expected the chances of passing a turn go to zero for large turn numbers.
The expression for losing on turn is simpler, just
The cumulative probability of losing on turn 1, or turn 2, or … turn is the same sum as above, approaching – everyone loses eventually!
When do I expect to lose
Getting back to the main point, when are these games lost on average? Plotting for a range of below, the number of turns goes up very slowly with .
It’s unlikely to lose too early, but also unlikely to lose too late. The distribution, as with all things, starts to look quite gaussian for large (exercise for the reader: show this by expanding about its maximum).
The expected turn to lose on is simply the sum over . There is no normalising constant as we showed above that .
Performing this sum,
What a lovely result! Here it is plotted against some numerical tests.
One might have immediately suspected that logarithms were involved, given that the game involves repeatedly shrinking a number by some proportion. In fact, if there was no losing involved you can show that the expected number drawn on each turn is , i.e. on average the numbers halve each turn. The tricky part is incorporating the probability of losses, which manifests here as a trimming of the probability distributions below .
Repeat for a loss at an arbitrary number rather than 1.
Repeat for the discrete case where and are integers.
Compute the limiting distribution of probability of loss over turns for large .