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?

Note by C Lim
6 years ago

No vote yet
6 votes

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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 nn consecutive H's decreases rapidly as nn 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 - 6 years ago

Log in to reply

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

C Lim - 6 years ago

Log in to reply

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

112+214+318+4116+5132+=2. 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

312+614+918+12116+15132+=32=6. 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>46 > 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 - 6 years ago

Log in to reply

@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=b+12+12a = \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=a+12+b+12b = \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=a+12+12,b=a+12+b+12 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 - 6 years ago

Log in to reply

@C Lim That's really great. Two completely different ways of solving the problem :) I wouldn't know how to prove that a,ba,b are finite though.

Tim Vermeulen - 6 years ago

Log in to reply

@Tim Vermeulen If you want a finiteness proof, use first principles. Let NAN_A be the number of tosses until AA stops. The probability P[NA>n]P[N_A>n] is the probability that AA has not thrown HT in the first nn tosses. This can only happen if AA has thrown jj tails followed by njn-j heads, for some 0jn0 \le j \le n. Thus there are n+1n+1 possible sequences, all equally likely, and so P[NA>n]=(n+1)2n P[N_A > n] = (n+1)2^{-n} Thus P[NAn]  =  P[NA>n1]  =  n21n P[N_A \ge n] \;=\; P[N_A > n-1] \; = \; n2^{1-n} Normal probability and series summation tricks give us E[NA]  =  n=1P[NAn]  =  n=1n21n  =  4 E[N_A] \;=\; \sum_{n=1}^\infty P[N_A \ge n] \; = \; \sum_{n=1}^\infty n2^{1-n} \; = \; 4 The result for BB is a little more challenging. Let NBN_B be the number of tosses until BB stops. The probability that NB>nN_B > n is the probability that BB does not throw HH in the first nn tosses. This is the probability that the first nn tosses are made up of "HT"s and "T"s stuck together, plus the probability that the first n1n-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×1n\times1 chess-board using just 2×12\times1 dominoes and 1×11\times1 squares is the Fibonacci number Fn+1F_{n+1}. (Just to be definite, F0=0F_0=0, F1=1F_1=1, etc.) Thus the probability that NB>nN_B > n is the sum of the probabilities Fn+12nF_{n+1}2^{-n} and Fn2nF_n2^{-n}, and hence P[NB>n]  =  Fn+22n P[N_B > n] \; = \; \frac{F_{n+2}}{2^n} and hence P[NBn]  =  P[NB>n1]  =  Fn+12n1n1. P[N_B \ge n] \; = \; P[N_B > n-1] \; = \; \frac{F_{n+1}}{2^{n-1}} \qquad n \ge 1. Thus E[NB]  =  n=1P[NBn]  =  n=1Fn+12n1  =  4G(0.5)2 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)  =  n=0Fnxn G(x) \;=\; \sum_{n=0}^\infty F_nx^n is the generating function of the Fibonacci numbers. It is well-known that G(x)  =  x1xx2 G(x) \; = \; \frac{x}{1-x-x^2} so that G(0.5)=2G(0.5) = 2. Thus E[NB]=6E[N_B] = 6.

Mark Hennings - 6 years ago

Log in to reply

@Mark Hennings Of course, once you showed that the number of ways is Fn+2 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 - 6 years ago

Log in to reply

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

Calvin Lin Staff - 6 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:

(IHTHTTHTTHHI012120000H000120012T000012120HT000012120TH000120012TT000012120HH0000001) \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:

(0121200000012000000121200001212000120000001212) \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 (IQ)1(I-Q)^{-1} is:

(1121213232010111001122000222000121000123) \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 - 6 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...