Puzzle: Paradox in Probability

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?

#Combinatorics #Riddles #MathProblem #Math

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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.

Tim Vermeulen - 7 years, 10 months ago

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

C Lim - 7 years, 10 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)?

Tim Vermeulen - 7 years, 10 months ago

@Tim Vermeulen – 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. ]

C Lim - 7 years, 10 months ago

@C Lim – 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.

Tim Vermeulen - 7 years, 10 months ago

@Tim Vermeulen – 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$ .

Mark Hennings - 7 years, 10 months ago

@Mark Hennings – 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.

Calvin Lin Staff - 7 years, 10 months ago

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

Calvin Lin Staff - 7 years, 10 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.

gopinath no - 7 years, 10 months ago

Math	Appears 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}$