Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
See this. –  David Mitra Apr 29 '13 at 15:06
add comment

marked as duplicate by Ross Millikan, Davide Giraudo, Arkamis, 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.

1 Answer

up vote 3 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}$

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

share|improve this answer
add comment

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