Infinite coin flipping

Suppose Alice and Bob decide to play the following simple game: they alternate turns flipping a coin, and whoever gets heads first immediately wins. (Alice gets the privilege of going first.) What are Alice’s chances of winning this game?

To make it more general, let’s suppose the coin is heads with probability \( x \), where \( 0 \le x \le 1 \). There are two approaches to solving this problem. Let’s look at the ‘brute force’ way first. Alice only gets to flip the coin on the first, third, fifth, seventh, … turns. Thus, her chances of winning the game must be equal to the infinite sum of her chances of winning on each of those respective turns. On the first turn, her chance of winning is \( x \). In order to win on turn three, all previous flips must have been tails. Thus, her chances of winning in this case are \( (1-x)^{2} x \). Similarly, on turn five, her chances of winning are \( (1-x)^{4} x \), and this suggests that on turn \( 2n + 1 \), her chances of winning are \( (1-x)^{2n} x \). Thus, her chances of winning the game in total are

\( \displaystyle \sum_{n=0}^{\infty} (1-x)^{2n} x. \)

This is a geometric series with first term \( x \) and ratio \( (1-x)^{2} \), so it is equal to \( \frac{x}{1 – (1-x)^{2}} = \frac{x}{2x – x^{2}} = \frac{1}{2 – x}. \) So for instance, if the coin is fair, \( x = \frac{1}{2} \) and Alice’s chances of winning are \( \frac{1}{2 – \frac{1}{2}} = \frac{2}{3}. \)

While this approach certainly was successful, let’s look at a slicker alternative. Starting over, let’s denote the probability that Alice wins the game by \( P \). Then of course the probability that Bob wins the game is \( 1 – P \). Instead of putting ourselves in Alice’s shoes, let’s pretend for a minute that we are Bob. Suppose Alice goes first and throws tails. Now, as Bob, we are pretty happy! It’s almost as though we get to go first now …

Well wait a minute, it is exactly as though we get to go first now! This observation actually tells us something: the original probability of Bob winning the game must be equal to the probability of Alice winning the game while first throwing tails. In equations, this means that \( (1 – P) = P(1 – x) \). Now we can simply solve for \( P \):

\( 1 = P(1-x) + P \)

\( 1 = P(2 – x) \)

So \( P = \frac{1}{2-x} \), just as before. (Notice that our answer makes intuitive sense: as \( x \searrow 0 \), Alice’s probability of winning approaches \( \frac{1}{2} \) from above, and as \( x \nearrow 1 \), Alice’s probability of winning approaches \( 1 \) from below.)

This approach to probability is essentially recursive, and we’ll see more of it in the next post.

Leave a Reply