Here's a cute puzzle.

Player A tosses a coin indefinitely and stops when he encounters a consecutive sequence of HT. Player B plays a similar game, except he stops when he encounters HH consecutively. Is the expected number of tosses equal for both players? If not, who has more, and can you give an intuitive explanation why?

## Comments

Sort by:

TopNewestI think that player A is expected to be finished earlier. If he encounters an H, then he would have to keep tossing H's in order to continue. The chance of throwing \(n\) consecutive H's decreases rapidly as \(n\) increases.

If player B encounters an H, then he will have to toss a T to continue, but after tossing a T, he will continue tossing, because no matter what he tosses next, he doesn't encounter HH.

So, player A is doomed so to say whenever he tosses an H, because he'll have to keep tossing H's in order to continue. That's why he is expected to stop earlier than player B. I hope that makes sense. – Tim Vermeulen · 4 years ago

Log in to reply

– C Lim · 4 years ago

Yup that's correct! It would also be interesting to explicitly calculate the expected number of throws for both A and B.Log in to reply

\[ 1 \cdot \frac{1}{2} + 2 \cdot \frac{1}{4} + 3 \cdot \frac{1}{8} + 4 \cdot \frac{1}{16} + 5 \cdot \frac{1}{32} + \dots = 2. \]

Similarly, after having tossed his first H, player A is expected to throw his first T (and thus stopping) after another 2 tosses. So (hopefully) I can conclude that player H is expected to toss 4 times.

Player B is expected to roll his first H in two tosses. Then, there is a chance of 50% that he stops after the third toss, i.e. after tossing H again. However, if he tosses a T, then again, he is expected to toss his second H in two tosses, after which there is a 50% chance that he stops after the toss after that. It goes on and on. So, the amount of tosses player B is expected to do is

\[ 3 \cdot \frac{1}{2} + 6 \cdot \frac{1}{4} + 9 \cdot \frac{1}{8} + 12 \cdot \frac{1}{16} + 15 \cdot \frac{1}{32} + \dots = 3 \cdot 2 = 6. \]

And \(6 > 4\).

I hope that what I did is allowed, I'm not completely convinced of that just yet. Could anyone confirm that what I did is correct (or show me what I've done wrong)? – Tim Vermeulen · 4 years ago

Log in to reply

Here's how I'd do it. To compute the expected number of tosses for HH, we define two values:

Then \(a = \frac{b+1} 2 + \frac 1 2\) since if the previous toss was 'H', there's a 50% chance the next is 'T' (in which case the expected number of tosses is b+1), and a 50% chance the next is 'H' (in which case the number of tosses is 1 since it ends).

Likewise, \(b = \frac{a+1} 2 + \frac{b+1}2\) since if the previous toss was 'T', there's a 50% chance the next is 'H' (in which case expected number of tosses is a+1), and a 50% chance the next is 'T' (and the expected number of tosses is b+1).

Solving then gives us a=4, b=6. The expected number of tosses is then b=6, since we can assume the 0-th toss was 'T' with no loss of generality.

The equations for HT are similar:

\[ a = \frac {a+1} 2 + \frac 1 2, \quad b = \frac{a+1}2 + \frac{b+1} 2\]

which gives us a=2, b=4.

[ P.S. To be pedantic, my working isn't 100% rigourous either, since it already assumes a, b are finite. ] – C Lim · 4 years ago

Log in to reply

– Tim Vermeulen · 4 years ago

That's really great. Two completely different ways of solving the problem :) I wouldn't know how to prove that \(a,b\) are finite though.Log in to reply

It is well-known that the number of ways of tiling a \(n\times1\) chess-board using just \(2\times1\) dominoes and \(1\times1\) squares is the Fibonacci number \(F_{n+1}\). (Just to be definite, \(F_0=0\), \(F_1=1\), etc.) Thus the probability that \(N_B > n\) is the sum of the probabilities \(F_{n+1}2^{-n}\) and \(F_n2^{-n}\), and hence \[ P[N_B > n] \; = \; \frac{F_{n+2}}{2^n} \] and hence \[ P[N_B \ge n] \; = \; P[N_B > n-1] \; = \; \frac{F_{n+1}}{2^{n-1}} \qquad n \ge 1.\] Thus \[ E[N_B] \; = \; \sum_{n=1}^\infty P[N_B \ge n] \; = \; \sum_{n=1}^\infty \tfrac{F_{n+1}}{2^{n-1}} \; = \; 4G(0.5) - 2 \] where \[ G(x) \;=\; \sum_{n=0}^\infty F_nx^n \] is the generating function of the Fibonacci numbers. It is well-known that \[ G(x) \; = \; \frac{x}{1-x-x^2} \] so that \(G(0.5) = 2\). Thus \(E[N_B] = 6\). – Mark Hennings · 4 years ago

Log in to reply

Nice way of calculating the sum through generating functions. – Calvin Lin Staff · 4 years ago

Log in to reply

In a similar vein, check out High school math #8. – Calvin Lin Staff · 4 years ago

Log in to reply

The absorbing Markov chain also gets the same answer.

This is the markov chain for ending the game with HH, for player B. I is the initial state, and the probabilities of moving to different states are shown:

\( \left(\begin{array}{cccccccc} & I & H & T & HT & TH & TT & HH \\ I & 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 \\ H & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ T & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ HT & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ TH & 0 & 0 & 0 & \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ TT & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ HH & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right) \)

Matrix Q is:

\( \left(\begin{array}{rrrrrr} 0 & \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{array}\right) \)

Fundamental matrix \((I-Q)^{-1}\) is:

\( \left(\begin{array}{rrrrrr} 1 & \frac{1}{2} & \frac{1}{2} & 1 & \frac{3}{2} & \frac{3}{2} \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 2 & 2 \\ 0 & 0 & 0 & 2 & 2 & 2 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 1 & 2 & 3 \end{array}\right) \)

The required expectation is the sum of the first row, which is 6.

Similarly doing for the 'HT' case yields an expected value of 4. – Gopinath No · 4 years ago

Log in to reply