Nice probability puzzle

For the last few weeks, Chris Maslanka's excellent maths puzzle column in the Guardian has been running variants on the following problem. Fred and Sam play a game in which the winner is the first to flip a head. They take it in turns, Fred starting. What's the chance that Fred wins? I have been asking this to 6th form audiences and the general response is 2/3 or 3/4, but nobody can say why. Here is the solution I have been using.

Let Fred's chance of winning the game be [math]p[/math]. Fred has [math]1/2[/math] chance of winning immediately, but if he flips a tail, with probability [math]1/2[/math], then the coin passes to Sam who now is in exactly the same position as Fred was when he started. So Sam's chance of winning must now be p, so Fred's is [math]1-p[/math]. So Fred's overall chance of winning must obey the equation
[display]p = 1/2 + 1/2 (1-p)[/display]
which can be solved to give [math]p =2/3[/math].

Here is a probability tree that explains it.

Probability tree for Fred and Sam competing to flip a head first

I like this puzzle as it combines algebra with probability, my two favourite bits of maths. It must be a classic and no doubt has a name. Mike Pearson identified this elegant explanation involving a graphical means of dividing a square into three equal areas: suppose that on the first flip, Fred wins on green or blue, then if he fails the second flip corresponds to the top half of diagram, Sam wins on orange, then if he fails we're back to where we were at the start but now in the top-right-hand corner of the diagram. So the probability Fred wins is the total green and blue area (2/3), Sam wins on total orange area (1/3).

trisection of a square

Chris Maslanka has used versions for which the winning event does not have probability 1/2: last week the winner had to throw two dice and the product of the faces be odd (probability 1/4 of occurring), which is a neat way of combining two questions in one. In general, if the winning event has probability [math]w[/math], then Fred's chance of winning the game obeys the equation
[display]p = w + (1-w) (1-p)[/display]
which can be solved to give
[display]p = \frac{1}{2-w}.[/display]
So if the chance of the winning event is [math]w = 1/4[/math], then the person who starts first has [math]p = 4/7[/math] chance of eventually winning the game.

We can also rearrange to find that
[display]\frac{p}{1-p} = \frac{1}{1-w};[/display]
that is the odds [math]p/(1-p)[/math] of winning the game is [math]1/(1-w)[/math]. So if $w= 1/4$, then the odds of the starter winning the game is 4 to 3.

Finally, we can generalise the game to $N$ players. Suppose we assume they have probabilities $p_1, p_2, ..., p_N$ of winning the game. The trick is then to realise that if the first person fails to win immediately, the probabilities of winning the game change to $p_N, p_1, p_2..., p_{N-1}$. Consider the chance $p_2$ of the second player winning: when person 1 starts the game, either

• they will win immediately with probability $w$, in which case the chance of person 2 eventually winning becomes 0,
• or person 1 will fail with probability $1-w$, in which case the chance that person 2 eventually wins becomes $p_1$.

So the chance, $p_2$, of the second player winning is given by
[display]p_2 = w \times 0 + (1-w) p_1[/display]
So $p_2 = (1-w)p_1$, and by a similar argument $p_{i} = (1-w)p_{i-1}$, leading to $p_{i} = (1-w)^{i-1}p_1$. The sum of all the probabilities is
[display]p_1 + p_2 + .. + p_N = p_1[1 + (1-w) + .. (1-w)^{N-1}] = p_1 S [/display]
where the sum $S = (1 - (1-w)^N)/w$ using standard identities. Since the sum of the probabilities must be 1, we obtain that the chance that the first person wins is
[display]p_1 = \frac{w}{1-(1-w)^N}[/display]
and in general
[display]p_i = \frac{w (1-w)^{i-1}}{1-(1-w)^N}.[/display]

So, for example, if $N=4$ people play a game in which they flip two coins and the first to get 2 heads wins ($w = 1/4$), then the chances of each of the four people eventually winning are $\frac{64}{175}, \frac{48}{175}, \frac{36}{175}, \frac{27}{175}.$