The expected value for 7 heads in a row

[AllRelative]

Homework Statement

We have a coin with probability $0\leqslant p \leqslant 1$ of getting heads. We flip the coin until we get $7$ heads in a row. Let $N_7$ be the number of necessary flips to get the $7$ heads in a row.

What is the expected value $E(N_7)$?

Homework Equations

The prof suggested using this:
$E(N_7) = E[E(N_7| N_6)]$

I also found online the law of iterated expectation which is: $\sum_{i=1}^{n} E[X | A_i]P(A_i) = E(X)$

The Attempt at a Solution

We learned about conditional expectation this morning in class. We still haven't done any example. I'm unsure about what this notation really mean.

Does the law of iterated expectation looks like this for this problem?

$$\sum_{i=1}^{6} E[N_7 | N_i]P(N_i) = E(N_7)$$
$$E[N_7 | N_1]P(N_1)+E[N_7 | N_2]P(N_2)+...+ E[N_7 | N_6]P(N_6)$$

And if so, is $P(N_2) = p ^2$?
And how do I evaluate of the $E[N_7 | N_i]$?

Thanks!

 

[StoneTemplePython]

Homework Equations

The prof suggested using this:
$E(N_7) = E[E(N_7| N_6)]$
...

And how do I evaluate of the $E[N_7 | N_i]$?

a typical suggestion of mine: start simple and build.

In this case first solve:
$E(N_1) = E[E(N_1| N_0)]$ and $E(N_2) = E[E(N_2| N_1)]$

We learned about conditional expectation this morning in class. We still haven't done any example. I'm unsure about what this notation really mean.

This is going to be a significant issue and I'd recommend working quite a few examples in full before tackling this problem.

There are a lot of ways to solve this problem, a couple of which have been fairly recently done in this forum. With some cleverness it can even be done by drawing a tree and solving a system of equations (using backward induction).

edit: what text are you using? There has got to be some fully worked examples in your text.

 

[Ray Vickson]

Homework Statement

We have a coin with probability $0\leqslant p \leqslant 1$ of getting heads. We flip the coin until we get $7$ heads in a row. Let $N_7$ be the number of necessary flips to get the $7$ heads in a row.

What is the expected value $E(N_7)$?

Homework Equations

The prof suggested using this:
$E(N_7) = E[E(N_7| N_6)]$

I also found online the law of iterated expectation which is: $\sum_{i=1}^{n} E[X | A_i]P(A_i) = E(X)$

The Attempt at a Solution

We learned about conditional expectation this morning in class. We still haven't done any example. I'm unsure about what this notation really mean.

Does the law of iterated expectation looks like this for this problem?

$$\sum_{i=1}^{6} E[N_7 | N_i]P(N_i) = E(N_7)$$
$$E[N_7 | N_1]P(N_1)+E[N_7 | N_2]P(N_2)+...+ E[N_7 | N_6]P(N_6)$$

And if so, is $P(N_2) = p ^2$?
And how do I evaluate of the $E[N_7 | N_i]$?

Thanks!

I cannot easily get the answer using your notions and notation. The problem is that there are two aspects: where you are now, and how far you need to go. Here is what I mean: suppose we define the state to be the length of the current H run, so state 0 means "0 heads so far = start, or re-start", 1 means "run of 1 heads so far", 2 means "run of 2 heads so far", etc. State 7 = "run of 7 heads so far = we are done". Let $T_i$ = remaining number of tosses needed to get to state 7, starting from state $i$, and let $x_i = E(T_i).$ We want to compute $x_0.$

When we are in state 0, we go next to state 1 if we get Heads and back to state 0 if we get Tails. So, after 1 toss, the tosses left are $T_1$ if Heads and $T_0'$ if Tails. Here, the $T_0'$ is a random copy of the original $T_0$; that is, it has the same probability distribution as the original random variable $T_0$. Basically, if you get Tails you go back to the beginning and start over, just as though the problem were brand new. The "history" of how you got back to state 0 is wiped out, because the coin has no memory. Similarly, when we are currently in state 3 (just having completed a usable H-run of length 3), we don't know if we are at our third toss or our 150th toss; the history of how we got to state 3 currently is wiped out---again because the coin has no memory.

Taking expectations of the equation
$$T_0 = 1 + \begin{cases} T_1 & \text{if Heads}\\
T_0' & \text{if Tails}
\end{cases} $$
we get
$$x_0 = 1 + p x_1 + q x_0, $$ where $q = 1-p.$ Similarly,
$$\begin{array}{rcl}x_1 &=&1 + p x_2 + q x_0\\
x_2 &=&1 + p x_3 + q x_0 \\
\vdots & \vdots &\hspace{4ex} \vdots
\end{array} $$
We have $x_7 = 0$, so we get a solvable system.

If you use generating functions
$$\tilde{T}_i(z) = E z^{T_i} = \sum_{n=0}^\infty P(T_i = n) z^n$$ with $\tilde{T}_7(z) \equiv 1,$ you will have a solvable system
$$\tilde{T}_i(z) = p z \tilde{T}_{i+1}(z) + q z \tilde{T}_0 (z), i=0,1, \ldots, 6$$ You can use the generating functions to get things like $P(T_i = n)$, $\text{Var}(T_i),$ etc.

 

[haruspex]

$E(N_7) = E[E(N_7| N_6)]$

This is a misleading notation. The N₇ has been defined as a random variable, but the N₆ is being used as a state.
It is clearer to define E(n,r) as the expected number of furher tosses to reach n consecutive given that the last r were all heads. Thus E(n,n)=0. (I'm guessing this is what your prof has in mind.)
Can you express E(n,r) in terms of E(n,r+1) and E(n,0)?

 

[WWGD]

Worse case, if you get stuck in the exam: Can get 7 heads in a row after : 7,8,9,... , though the general form becomes more complicated after 7, but still manageable; just make sure that you get a tails right before the streak of 7 .

 

[StoneTemplePython]

I agree that as is, the notation currently stated can lead to potentially very big problems. I also get the impression that OP has disappeared.

- - --
The simplest (albeit somewhat tedious) approach I could think of is to use "first step analysis".

That is, you start the experiment and toss a coin over and over until the pattern comes up. In particular consider the outlook after tossing the coin 7 times. Since we are interested in a run of 7 heads, considering the first 7 tosses is a natural "first step" of the process.

With probability $p^7$ the experiment is over in exactly 7 tries because they were all heads. With probability $1-p^7$ you get a fresh start (this is akin to a memorylessness argument for geometric distribution). On top of this there is a "residual" (expected value of finite/truncated geometric distribution) to layer in -- this residual step isn't so complicated but is a little unpleasant. The idea is that your fresh start doesn't necessarily occur after 7 tosses -- it could have occurred after 1 turn or 2 turns or 3 turns or ... or 7 turns. (This is the idea of overlaps in between trials.)

These are only 3 building blocks needed to calculate $E\big[N_7\big]$. This approach has the added benefit of highlighting parallels with a geometric distribution and the distinction/complication which is due to the issue with overlaps.

 

[WWGD]

I agree that as is, the notation currently stated can lead to potentially very big problems. I also get the impression that OP has disappeared.

- - --
The simplest (albeit somewhat tedious) approach I could think of is to use "first step analysis".

That is, you start the experiment and toss a coin over and over until the pattern comes up. In particular consider the outlook after tossing the coin 7 times. Since we are interested in a run of 7 heads, considering the first 7 tosses is a natural "first step" of the process.

With probability $p^7$ the experiment is over in exactly 7 tries because they were all heads. With probability $1-p^7$ you get a fresh start (this is akin to a memorylessness argument for geometric distribution). On top of this there is a "residual" (expected value of finite geometric series) to layer in -- this residual step isn't so complicated but is a little unpleasant. The idea is that your fresh start doesn't necessarily occur after 7 tosses -- it could have occurred after 1 turn or 2 turns or 3 turns or ... or 7 turns. (This is the idea of overlaps in between trials.)

These are only 3 building blocks needed to calculate $E\big[N_7\big]$. This approach has the added benefit of highlighting parallels with a geometric distribution and the distinction/complication which is due to the issue with overlaps.

Great minds think alike -- and at the same time :). We wrote the same answer at the same time.

 

[haruspex]

My approach, in post #4, is E(n,r)=1+½(E(n,r+1)+E(n,0)) for r<n, and E(n,n)=0.
Trying E(n,r)=A.2^r+B we easily find A and B that satisfy the recurrence relation and boundary condition.

 

[Ray Vickson]

My approach, in post #4, is E(n,r)=1+½(E(n,r+1)+E(n,0)) for r<n, and E(n,n)=0.
Trying E(n,r)=A.2^r+B we easily find A and B that satisfy the recurrence relation and boundary condition.

That recurrence is OK when $p = 1/2$, but not for general $p \in (0,1).$

 

[haruspex]

That recurrence is OK when $p = 1/2$, but not for general $p \in (0,1).$

Ah yes, I forgot the question is more general, but the same approach works.
E(n,r)=1+pE(n,r+1)+(1-p)E(n,0) for r<n, and E(n,n)=0.
Trying E(n,r)=A.λ^r+B, etc...

 

[Ray Vickson]

Ah yes, I forgot the question is more general, but the same approach works.
E(n,r)=1+pE(n,r+1)+(1-p)E(n,0) for r<n, and E(n,n)=0.
Trying E(n,r)=A.λ^r+B, etc...

Yes, I agree. That is what I outlined in post #3, but with different notation.