An interesting probability game

I came across a fascinating puzzle while perusing the book Game Theory Evolving.

This problem is a bit more challenging mathematically, but I hope some of you will find it interesting. Here it is:

Bob tells Alice to draw repeatedly from the uniform distribution on [0,1] until her current draw is less than some previous draw, and he will pay her $n, where n is the number of draws. What is the average value of this game for Alice?

Can you solve it? The answer is below.

The answer

The book offers the following elegant solution which I will describe in detail.

Step 1: write the value algebraically

Let p_n correspond to the probability the game ends on the n^th draw. Then the expected value V is

V = 2p₂ + 3p₃ + 4p₄ + 5p₅ + …

This expression is another way of stating the payoff rule that Bob will pay Alice n dollars if she gets to draw n. The formula merely expresses the rule mathematically and is a summation to represent the expected value.

Step 2: note the minimum payoff

One thing to notice is the game can earliest end on draw number 2. This is because the first draw is how the game starts–by definition it cannot be smaller than any previous draws.

Thus, the value of the game is at least 2 dollars. Moreover, the game can really be viewed as starting from the second draw and proceeding onwards. The value of the game can thus be re-written as:

V = 2 + p₃ + 2p₄ + 3p₅ + …

In comparison to the first formula for the value of the game, two major things have changed. First, the term p₂ has vanished because the game never ends before turn 2. Second, the dollar payoffs attached to the probabilities are decremented by two, as the game is now viewed as starting from the second turn and the term 2 is already included as the first summand.

Step 3: group the sums

This step is the hardest part. It’s a trick of grouping some of the terms so the sums make sense.

This is a technique used in lots of college level math courses, but even with practice, I admittedly did not figure this out.

The trick is this. Notice that each term after p₃ has a coefficient one larger than the term before it. This means we can express the sum as follows:

V = 2 + (p₃ + p₄ + p₅ + … ) + (p₄ + p₅ + … ) + (p₅ + … ) + …

If you account carefully, you’ll see that the term p₃ appears exactly once, the term p₄ appears exactly twice, and so on so that this grouped summation is just another way of writing the previous formula.

Step 4: interpret the grouped sums

We’re almost there to calculate the sum.

The sums were grouped in this way because they have a special interpretation. The grouped sums represent the chance that the game ends on that turn or later. For instance, the first grouped sum in parenthesis corresponds to the sum of all the probabilities of the game ending on after turn 2 or later. Similarly, the second grouped corresponds to the chance the game ends after turn 3 or later, and each subsequent grouped sum has a corresponding interpretation.

The value of the the game is therefore:

V = 2 + Prob(n > 2) + Prob(n > 3) + Prob(n > 4) + …

This simplifies the problem considerably. Now it only remains to calculate the probability of the game ending continuing after a particular draw.

Step 5: a formula for Prob(n > k)

I am not going to be completely rigorous on the math, but here’s the general idea.

What’s the chance that Alice will draw past turn 2? This can be answered by thinking combinatorially.

On the second draw, Alice has picked out two numbers, say a and b. The numbers could either have been picked in the order (a, b) or (b, a), both equally likely.

If the order Alice picked corresponds to the increasing sequence, that that means the game would continue. There is obviously a 1/2 chance she picked the order in this way.

What about turn 3? At this point, Alice has picked three numbers, a, b, and c. How many sequences are possible? There are 6 = 3!, namely:

a, b, c
a, c, b
b, a, c
b, c, a
c, a, b
c, b, a

Now the game ends if Alice ever picks a smaller number than some previous draw. In other words, the game ends if the sequence ever decreases in size.

That means the only way the game could have reached this point and still continue is if the sequence is strictly increasing. There’s obviously one way for this to happen–Alice has to keep picking larger and larger terms.

This means the probability is 1/6 = 1/3! that Alice reached this possibility.

The pattern will continue, and we can generalize that the game would reach beyond turn n with probability 1/n!, where n! = n x (n – 1) x (n – 2) … x 1

Now we can substitute this in the formula for the value of the game, which becomes:

V = 2 + 1/2! + 1/3! + 1/4! + … = 2.71818… = e

It’s rather remarkable that e appears in the solution!

Although perhaps this is a natural thing to expect, as Euler’s number comes up in another problem I covered about the game theory of love.