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?

Note by C Lim
4 years, 8 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

I 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.

- 4 years, 8 months ago

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

- 4 years, 8 months ago

Player A is expected to throw his first H after $$2$$ tosses, because

$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)?

- 4 years, 8 months ago

I'm not sure what you did is ok either, but your answer is correct! [ This suggests there's probably a way to rigourously justify your working. ]

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

• let a = expected number of additional tosses, assuming previous was 'H';
• let b = expected number of additional tosses, assuming previous was 'T'.

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. ]

- 4 years, 8 months 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.

- 4 years, 8 months ago

If you want a finiteness proof, use first principles. Let $$N_A$$ be the number of tosses until $$A$$ stops. The probability $$P[N_A>n]$$ is the probability that $$A$$ has not thrown HT in the first $$n$$ tosses. This can only happen if $$A$$ has thrown $$j$$ tails followed by $$n-j$$ heads, for some $$0 \le j \le n$$. Thus there are $$n+1$$ possible sequences, all equally likely, and so $P[N_A > n] = (n+1)2^{-n}$ Thus $P[N_A \ge n] \;=\; P[N_A > n-1] \; = \; n2^{1-n}$ Normal probability and series summation tricks give us $E[N_A] \;=\; \sum_{n=1}^\infty P[N_A \ge n] \; = \; \sum_{n=1}^\infty n2^{1-n} \; = \; 4$ The result for $$B$$ is a little more challenging. Let $$N_B$$ be the number of tosses until $$B$$ stops. The probability that $$N_B > n$$ is the probability that $$B$$ does not throw HH in the first $$n$$ tosses. This is the probability that the first $$n$$ tosses are made up of "HT"s and "T"s stuck together, plus the probability that the first $$n-1$$ tosses are made up of "HT"s and "T"s stuck together, followed by a single "H".

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$$.

- 4 years, 8 months ago

Of course, once you showed that the number of ways is $$F_{n+2}$$, you can use the ratio test to conclude that the sum is finite, which is all we needed.

Nice way of calculating the sum through generating functions.

Staff - 4 years, 8 months ago

In a similar vein, check out High school math #8.

Staff - 4 years, 8 months ago

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.

- 4 years, 8 months ago