Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

The question is pretty much in the title. How many flips of a fair coin does it take until you get N heads in a row on expectation? I am curious how this is proven in terms of probability (no this is not for homework, just genuine curiosity as it's a question I've always wondered).

share|cite|improve this question

marked as duplicate by Ross Millikan, Davide Giraudo, Emily, Amzoti, TMM Apr 29 '13 at 15:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

See this. – David Mitra Apr 29 '13 at 15:06
up vote 7 down vote accepted

Let $p$ be the probability of flipping a heads. Let $x$ be number of flips needed to achieve $h$ consecutive heads. The solution is $E(x)=\frac{1-p^h}{p^h(1-p)}$.

This expression may be derived as follows. The probability of being successful immediately is $p^r$. However, one might get a tails immediately. In that case, the number of flips needed is $1+E(x)$ (one flip has been used and we are back to the original position). We might get a heads and then a tails. In this case two flips have been used and we are back to the original position. Continue this up to $h-1$ heads followed by a tails in which case $h$ flips have been used and we are back to the original position.

$E(x) = hp^h + (1-p)[E(x)+1] + p(1-p)[E(x)+2] + p^2(1-p)[E(x)+3]+ ... + p^{h-1}(1-p)[E(x)+h]$

$E(x) = hp^h + (1-p)\sum_{i=0}^{h-1}p^i[E(x)+i+1]$

$E(x) = (1-p^h)E(x)+\sum_{i=0}^{h-1}p^i$

$E(x) = (1-p^h)E(x)+\frac{1-p^h}{1-p}$


share|cite|improve this answer
Nice answer but I am confused by one part? Why do you say that it is necessary to get back to the original position? For example the second term in the first line is p(1-p)[E(x)+2] implying you went heads then tails and so back to the beginning, but surely having two tails and then the consecutive run of heads would be equally valid (1-p)(1-p)[E(x)+2]? More generally it would seem that any combination of throws that does not contain 5 heads and and ends in a tail would be a valid start for the run of 5 heads? I realize I am wrong but would like to understand why I am wrong. – Bazman Jun 13 '15 at 11:09
sorry no I got it – Bazman Jun 13 '15 at 14:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.