6

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

This is what I thought, but is not correct. Can you please help me?

Glen_b
  • 257,508
  • 32
  • 553
  • 939
Aseem Goyal
  • 163
  • 5
  • @Glen_b i am practicing on my own . – Aseem Goyal Feb 06 '14 at 09:13
  • sorry , i didn't knew that , i was myself editing the post . you are welcome to edit as you like . – Aseem Goyal Feb 06 '14 at 09:24
  • I've incorporated both sets of edits. Please take a look and make sure it still expresses what you need. – Glen_b Feb 06 '14 at 09:30
  • The question at http://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 06 '14 at 15:19

1 Answers1

4

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} \, . $$

Zen
  • 21,786
  • 3
  • 72
  • 114
  • 1
    please explain in words , how you got the equation – Aseem Goyal Feb 06 '14 at 13:29
  • Is it better now? – Zen Feb 06 '14 at 14:17
  • 1
    (+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 06 '14 at 17:10
  • Good hint, whuber. – Zen Feb 06 '14 at 23:26