6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @Glen_b i am practicing on my own . $\endgroup$ – Aseem Goyal Feb 6 '14 at 9:13
  • $\begingroup$ sorry , i didn't knew that , i was myself editing the post . you are welcome to edit as you like . $\endgroup$ – Aseem Goyal Feb 6 '14 at 9:24
  • $\begingroup$ I've incorporated both sets of edits. Please take a look and make sure it still expresses what you need. $\endgroup$ – Glen_b Feb 6 '14 at 9:30
  • $\begingroup$ 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. $\endgroup$ – whuber Feb 6 '14 at 15:19
4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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