Here is a fun game of probability and statistics that I was told about this week. You have a game where you toss a coin and you win if you get three heads in a row. What is the average number of throws for a win?

Advertisements

April 21, 2009 by dberenstein

Here is a fun game of probability and statistics that I was told about this week. You have a game where you toss a coin and you win if you get three heads in a row. What is the average number of throws for a win?

Advertisements

%d bloggers like this:

on April 21, 2009 at 3:34 amsaintnekoWouldn’t the average number of flips taken vary with the amount of games played? If you played infinite amount of games, you would have results ranging from 3 flips to win to infinite flips. So maybe the answer is (.5infinite)-1.5 flips?

caveat, i know nothing about statistics or probability.

on April 21, 2009 at 3:46 amdberensteinNeko:

The average is exactly defined over an infinite such amount of game trials. You should also assume that the coin is fair.

on April 21, 2009 at 4:15 amMattClever! I guessed the naive answer of eight, but then I wrote a quick Monte Carlo simulation and found I was wrong. In reasoning out the right answer I found it useful to think iteratively; ie. the expected number of flips for 1, 2, and finally 3 heads in a row, and realizing that you needed to get n-1 heads in a row before you could try and get n heads in a row.

on April 21, 2009 at 6:04 amX4llduxDon’t know (yet!) how to calculate it, but simple simulation yield 14 as an anwser.

on April 21, 2009 at 6:53 amMattCool, my sim agrees with yours.

on April 21, 2009 at 7:47 amHB10

on April 21, 2009 at 7:55 amLuboš MotlI would calculate it via the AdS/CFT correspondence, in the large-N limit.

Classically, if we want N heads in row, the probability of having N of random ones in the right way is 1/2^N. But you will need twice as many throws, i.e. 2^{N+1}, to get there, because in average, the victorious one is in the middle.

For N heads in row, you need classically 2^{N+1} in average. It may be seen that the one-loop correction has to be N-independent. For complexified N, one has no black hole intermediate branch cuts in this simple theory of quantum gravity. One can determine the additive constant e.g. for N=1.

If we want 1 head in row, the probability that it happens after 1 throws is 1/2, after 2 throws is this plus 1/4, after 3 throws it is 1/8, and so on. Now, 1×1/2 + 2×1/4 + 3×1/8 + … = 2, by differentiating a geometric series. But 2^{1+1}=4, so we must subtract two.

The average is thus 2^{N+1}-2 for N heads in row. For N=3, one gets 14. For N=5, one would get 62, and so on.

on April 21, 2009 at 8:15 amX4llduxNice explanation http://people.ccmr.cornell.edu/~ginsparg/INFO295/mh.pdf

on April 21, 2009 at 11:23 amhaiseb1/(6*6*6)

on April 22, 2009 at 1:36 amJBHere is another (complicated) way of doing the same thing:

Denote heads (tails) by H (T). Let p be the probability of a H and q be the same for a T (of course p+q=1). There are 4 possible events with variable number of steps and probabilities:

————————————————————————————

Event | Name | Probability | Number of tosses involved

————————————————————————————

T | E1 | q | 1

————————————————————————————

HT | E2 | pq | 2

————————————————————————————

HHT | E3 | p^2 q | 3

————————————————————————————

HHH | E4 | p^3 | 3

————————————————————————————

Any sequence of events, say m1 of E1, m2 of E2 and m3 of E3, in all possible orders, followed by a *single* E4 is a win! For example, when m1=m2=m3=0, it means a win at the first attempt (first 3 tosses in a row, all yielding H).

In the case when some or all of the m-s are non-zero, the total number of tosses involved is (m1 + 2*m2 + 3* m3 + 3), the last 3 coming from tossing 3 heads in a row of course. The probability for such a sequence of events except the final three heads to happen is

P(m1,m2,m3) = multiplicity * {P(E1)}^{m1} * {P(E2)}^{m2} * {P(E3)}^{m3} = (m1+m2+m3)!/{m1!m2!m3!} * {q^m1} * {(pq)^m2} * {(p^2 q)^m3}

so that the total probability incorporating the final three heads is p^3 * P(m1,m2,m3). Here the multipliciy arises from the simple combinatoric excercise of permuting the 3 events E1, E2 and E3 occuring m1, m2 and m3 times respectively. The sum of P(m1,m2,m3) over m1,m2,m3 = 0 to infinity can be performed by a simple application of the binomial theorem, followed by a gemetric series. The final answer is 1/{1 – q(1+p+p^2)}, so that upon substituting q = (1-p) we have sum of the probabilities = 1/p^3; considering the final 3 heads, the probability is unity as expected of course (the sum of probabilities of *all* events ending with a row of 3 heads is one)!

So now, the average number of tosses required is the sum of (m1 + 2*m2 + 3* m3 + 3) * P(m1,m2,m3) * p^3 over m1,m2,m3 = 0 to infinity. The easiest way to evaluate this sum is to note that (m1 + 2*m2 + 3* m3)* P(m1,m2,m3) = {p*(d/dp)+ q*(d/dq)}P(m1,m2,m3) where d/dp and d/dq are partial derivatives (needs to be taken *before* imposing the constraint q = (1-p)). Therefore

sum of (m1 + 2*m2 + 3* m3)* P(m1,m2,m3) over m1,m2,m3 = {p*(d/dp)+ q*(d/dq)}{sum of P(m1,m2,m3) over m1,m2,m3} = (1+p+p^2)/p^6 – 3/p^3

after imposing the constraint at the last step. So finally the average of (m1 + 2*m2 + 3* m3 + 3) is (1+p+p^2)/p^3. For an unbiased coin p = 0.5 and hence the average number of steps is 14 as others have found.

— JB

on April 22, 2009 at 1:43 amdberensteinMy solution was very similar, so now I don’t have to publish it!

on April 22, 2009 at 2:03 amJBThe analogous thing for getting n H in a row is a simple extention of the above, so I would just provide the relevant expressions

The events are T, HT, HHT, …., H^{n-1}T, H^n with probabilities q, pq, p^2q, …., p^{n-1}q and p^n and number of tosses involved are obviously 1, 2, …, n and n (the last two events involve the same number of tosses).

The probability of m1 event 1, …, m_{n-1} event _{n-1} is p^n * P(m_1, …, m_{n-1}) where

P(m_1, …, m_{n-1}) = (m_1+…+m_{n-1})!/{m_1! * m_2! * … * m_{n-1}!}

The sum of P(m_1,..,m_{n-1}) is given by

Sum = 1/{1-q(1+p+…+p^{n-1})}

so that p^n * sum with q = (p-1) becomes unity.

The required number of tosses is going to be the average of (m_1 + 2*m_2 + … + n*m_{n-1} + n) and this would be, as before [p^n * {p*(d/dp) + q*(d/dq) + n} Sum]. The final result is

number of tosses = (1+p+p^2+…+p^{n-1})/p^n.

If p = 0.5 (unbiased coin) and n=5 for example, the answer is 62 as was obtained using AdS/CFT by Lubos 😉

on April 22, 2009 at 9:52 pmLuboš MotlI have refined my AdS/CFT solution so that it is now completely serious:

http://motls.blogspot.com/2009/04/waiting-for-n-heads-in-row.html

on April 22, 2009 at 11:32 pmdberensteinHi Lubos:

Thanks for the completion. Now it makes more sense. There was one phrase in your first derivation in the second paragraph that I couldn’t see how it worked (I had to ask for help on that one). I agree it’s a very nice way of getting the result.

on April 23, 2009 at 4:44 amLuboš MotlDear David, thanks for your nice words: the AdS words were meant as a joke, but the “ergodic” or “path integral” approach was more serious. An advantage is that if one forgets how to solve it exactly, an approximate version of the argument still generates a quasi-solution that is close to reality – while it is easy to get completely lost in the formalism of the “Hamiltonian” approaches. Thanks for a fun problem.

on April 22, 2009 at 11:47 pmlinkfeedr » Blog Archive » Waiting for N heads in a row - RSS Indexer (beta)[…] was found on The Reference Frame. Click here to visit the full article on the original website.David Berenstein offered us the following:ProblemYou toss a coin and you win if you get N heads in a row. What is […]

on April 23, 2009 at 3:42 pmLuboš MotlMathematician (a nick on my blog) has written (or found?) an amazing, one-line derivation of the formula. Use f(N) for the average number of throws (an “expectation value”) to get N heads in a row. Assume it exists.

How much does it change if you change N by one? You need to get obtain one additional head. With 50% probability, you get it. With 50% probability, you get a tail, so you have to start the heads from 0 after the next throw, and add f(N)+1 additional throws to those that you have done. Mathematically,

f(N) – f(N-1) = 0.5 x 1 + 0.5 x [f(N)+1]

which means f(N)=2f(N-1)+2. This recursion relation is trivial to solve, with the obvious f(0)=0 starting point, and one gets f(N) = 2 x (2^N -1).

on April 24, 2009 at 8:54 amHaelfixThat recursion relationship is very elegant and intuitive. Kudos to whoever found it.

on May 14, 2009 at 9:16 pmcdogThe recursive solution is just the Markov chain. For a pictoral representation, see:

http://people.ccmr.cornell.edu/~ginsparg/INFO295/mh.pdf

By far, the simplest explanation.

on May 14, 2009 at 9:32 pmcdogHow about this problem:

Let X be the number of tosses of a fair coin until 2 heads in a row. Let Y be the number of tosses of a fair coin until 3 heads in a row. What is the Probability X > Y?

I ran Monte Carlo to solve this. It should be 1-P(XY)=~21.24%

Anyone know how to solve this one rigorously?

on May 14, 2009 at 11:08 pmcdogSomething happened with the formatting there. The MC returns

Probability of X>Y =~ 21.24%