Coin Flipping Game

A Qualitative approach:

For Bob, as soon as he hits an $H$ , he will earn a point on the next $T$ . He has a $50 \%$ chance of winning every throw he doesn't win after the first $H$ in a given line.

However for Alice, her odds "reset" if she doesn't hit a second $H$ after her first. This means she must land another heads before her next $50 \%$ chance of winning.

Hence, If we view condition $1$ as either person flipping $H$ , and condition $2$ as scoring a point after condition $1$ is met, then Bob's condition $2$ failure IS condition 1 , whereas Alice's condition $2$ failure is NOT condition 1 .

Each condition is equally likely to be satisfied from either player, so this makes $\boxed{\text{Bob}}$ more likely to score more points.

As @Calvin Lin said below, the likelihood of seeing $HH$ or $HT$ is exactly identical, but it is only when looking at probability density in the long run, and the fact that we are using 2 different strings of flips, that we see the odds tip towards Bob

The solution becomes evident if we look at expected values of the lengths of “dry runs” for Alice and Bob before we score. For Alice we have the following system of equations:

$\displaystyle E_0 = \frac{1}{2} (1 + E_{H}) + \frac{1}{2} (1 + E_{T}) \\ \displaystyle E_T = \frac{1}{2} (1 + E_{H}) + \frac{1}{2} (1 + E_{T}) \\ \displaystyle E_H = \frac{1}{2} (1 + E_{T})$

For Bob, however, it looks as follows:

$\displaystyle E_0 = \frac{1}{2} (1 + E_{H}) + \frac{1}{2} (1 + E_{T}) \\ \displaystyle E_T = \frac{1}{2} (1 + E_{H}) + \frac{1}{2} (1 + E_{T}) \\ \displaystyle E_H = \frac{1}{2} (1 + E_{H})$

Solving for $E_{0}$ in both cases we see that in Alice’s case it’s 5, but in Bob’s case it’s 3, so Alice will on average score on every 6th flip and have an expected score of 16.7, while Bob will score on every 4th flip and have an expected score of 25 (which is very easy to verify by a simulation).

[This solution is not complete.]

Lemma: (Alice) Consider the game where we flip coins until we first get a HH. What is the probability density function for $N_{HH}$ , the number of coin flips?

In order for there to be exactly $n$ flips, we need:

• For the last 2 flips, it is a HH
• For the $n-2$ flip, it is a T (otherwise we just need n-1 flips)
• For the first $n-3$ flips, there are no two consecutive heads. Recall (not proving here) that the number of ways to get no two consecutive heads is $F_{n-1}$ , the Fibonacci number.

Thus, $P ( N = n ) = \frac{ F_{n-1}} { 2^n}$ . A quick sanity check shows that the sum of these probabilites is 1, since $\sum_{n=2}^{\infty} \frac{ F_{n-1}} { 2^n} = 1$ . $_\square$

Lemma: (Bob) Consider the game where we flip coins until we first get a HT. What is the probability density function for $N_{HT}$ , the number of coin flips.

In order for there to be exactly $n$ flips, we need:

• For the last 2 flips, it is a HT
• For the first $n-2$ flips, there is no HT. Once we get a H, it has to be H all the way. There are $n-1$ ways for the first H to appear.

Thus, $P (N=k) = \frac{n-1} { 2^n}$ . A quick sanity check shows that the sum of these probabilites is 1, since $\sum_{n=2}^{\infty} \frac{ n-1 } { 2^n} = 1$ . $_\square$

Let's summarize these results

From here, (not proven) since $P ( N_{HT} \leq k ) \geq P(N_{HH} \leq k )$ shows that Bob is more likely to have a shorter cycle, hence he is more likely to have more points than Alice.

(This is where the solution is incomplete) To properly do this, we have to calculate the PDF for the number of points that they get. For example, note that the probability they would get 50 points (all lines have length 2) is the same, but the probability that they will get 49 points favors Bob (2 lines of 3 or 1 line of 4). We then calculate $P ( B > A )$ .