# Closed form recurrence formula for getting N consecutive heads on a coin

I want to find the expected number of coin tosses to get $N$ heads in a row, where $p$ is the probability of getting a head in a single toss.

Let $F(N)$ be the expected number of tosses to get $N$ heads consecutively, so

$$F(N) = 1 + p F(N-1) + (1-p) F(N)$$

which gives

$$F(N) = 1/p + F(N-1)$$

With base condition : $F(1) = 1 + 1/p$

My logic is as follows:

if we get a head, in current toss we need to get N-1 more heads consecutively, but if we get a tail, we have to start over

• @Glen_b i am practicing on my own . – Aseem Goyal Feb 6 '14 at 9:13
• sorry , i didn't knew that , i was myself editing the post . you are welcome to edit as you like . – Aseem Goyal Feb 6 '14 at 9:24
• I've incorporated both sets of edits. Please take a look and make sure it still expresses what you need. – Glen_b Feb 6 '14 at 9:30
• The question at stats.stackexchange.com/questions/12174 is a generalization of this one; its answers show how to find the expected number of tosses to reach any specified pattern of heads and tails. – whuber Feb 6 '14 at 15:19

Let $T^{(k)}$ be the time it takes to see the first run of $k$ successes.
Let $X\sim\mathrm{Ber}(p)$ be independent of $T^{(k)}$ for every $k$. Then, $$T^{(k)} = (T^{(k-1)}+1)\, X + (T^{(k-1)}+1+T^{(k)}) \, (1 - X) \, ,$$ because, in words, if I see a success in the current trial, then the time to get $k$ consecutive successes is the time to get $k-1$ consecutive successes plus one (the current trial); but if I see a failure, the time to get $k$ consecutive successes is the time to get $k-1$ consecutive successes plus one (the current trial), plus itself, because the process restarted in distribution.
Defining $a_k=\mathrm{E}[T^{(k)}]$, we find the recurrence $$a_k = (a_{k-1}+1)\,p + (a_{k-1}+1+a_k)\,(1-p) \, ,$$ or $$a_k = \frac{a_{k-1}}{p}+\frac{1}{p} \, .$$
• (+1) By defining $b_k = a_k + 1/(1-p)$ you obtain the simpler recurrence $b_k = b_{k-1}/p$ with initial condition $b_0=1/(1-p)$. This is a geometric series with initial value $1/(1-p)$ and constant ratio $1/p$, which makes finding a closed formula for $a_k = b_k - 1/(1-p)$ very easy. – whuber Feb 6 '14 at 17:10