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?
-
Recent Posts
Archives
- 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
Plato on Woof Woof Pepe on Woof Woof dberenstein on Woof Woof Lubos Motl on Woof Woof Wyrd Smythe on Happy 3.1415926535…… Some More Blogs
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 n-1 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 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.
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 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
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^{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
I 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
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 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.
[...] 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, 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).
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 1-P(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%