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?
Probability game
April 21, 2009 by dberenstein
Posted in probability, Statistics  21 Comments
21 Responses
Comments are closed.

Recent Posts
Archives
 November 2017
 February 2016
 November 2015
 October 2013
 September 2013
 August 2013
 June 2013
 May 2013
 April 2013
 March 2013
 February 2013
 January 2013
 November 2012
 September 2012
 August 2012
 July 2012
 May 2012
 March 2012
 February 2012
 January 2012
 December 2011
 November 2011
 September 2011
 July 2011
 June 2011
 May 2011
 April 2011
 March 2011
 February 2011
 January 2011
 December 2010
 November 2010
 October 2010
 September 2010
 August 2010
 July 2010
 June 2010
 May 2010
 April 2010
 March 2010
 February 2010
 January 2010
 December 2009
 November 2009
 October 2009
 September 2009
 August 2009
 July 2009
 June 2009
 May 2009
 April 2009
 March 2009
 February 2009
 January 2009
 December 2008
 November 2008
 October 2008
 September 2008
Recent Comments
Wyrd Smythe on Whoop! Kate on Nobel Prize in Physics awarded… dberenstein on HEP job at UCSB Lubos Motl on HEP job at UCSB dberenstein on HEP job at UCSB Pages
Meta
Wouldn’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.
Neko:
The average is exactly defined over an infinite such amount of game trials. You should also assume that the coin is fair.
Clever! 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 n1 heads in a row before you could try and get n heads in a row.
Don’t know (yet!) how to calculate it, but simple simulation yield 14 as an anwser.
Cool, my sim agrees with yours.
10
I would calculate it via the AdS/CFT correspondence, in the largeN 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 oneloop correction has to be Nindependent. 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.
Nice explanation http://people.ccmr.cornell.edu/~ginsparg/INFO295/mh.pdf
1/(6*6*6)
Here 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 ms are nonzero, 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 = (1p) 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 = (1p)). 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
My solution was very similar, so now I don’t have to publish it!
The 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^{n1}T, H^n with probabilities q, pq, p^2q, …., p^{n1}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_{n1} event _{n1} is p^n * P(m_1, …, m_{n1}) where
P(m_1, …, m_{n1}) = (m_1+…+m_{n1})!/{m_1! * m_2! * … * m_{n1}!}
The sum of P(m_1,..,m_{n1}) is given by
Sum = 1/{1q(1+p+…+p^{n1})}
so that p^n * sum with q = (p1) becomes unity.
The required number of tosses is going to be the average of (m_1 + 2*m_2 + … + n*m_{n1} + 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^{n1})/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 😉
I have refined my AdS/CFT solution so that it is now completely serious:
http://motls.blogspot.com/2009/04/waitingfornheadsinrow.html
Hi 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.
Dear 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 quasisolution 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.
[…] 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 […]
Mathematician (a nick on my blog) has written (or found?) an amazing, oneline 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(N1) = 0.5 x 1 + 0.5 x [f(N)+1]
which means f(N)=2f(N1)+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).
That recursion relationship is very elegant and intuitive. Kudos to whoever found it.
The 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.
How 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 1P(XY)=~21.24%
Anyone know how to solve this one rigorously?
Something happened with the formatting there. The MC returns
Probability of X>Y =~ 21.24%