# Expected number of coin flips until observing $n$ of the same side

Question: Consider a coin which is flipped Heads with probability $p$ and Tails with probability $1-p$. Let $C_n$ be the number of tosses until we observe $n$ consecutive Heads or $n$ consecutive Tails (for the first time). Compute $\mathbb{E}[C_n]$.

I am able to determine the expected number of tosses until $n$ consecutive Heads with such a coin. But this relied conditional probability; namely, it involved conditioning upon the number of flips until the first Tail.

For this reason, I can't figure out how to modify my technique when I allow both Heads & Tails to satisfy the $n$-consecutive-flip property.

Also, this was from an old exam, so if there is a way to do this problem with reasonable time-constraints that would be great. Thank you

EDIT: Here's work for $H_n$ the number of tosses until we observe $n$ consecutive Heads.

Let $\mu = E[H_n]$ and $F$ denote the first instance of Tails. Then, $$\mu = \sum_{k=1}^\infty E[H_n \mid F=k] P(F=k) = \sum_{k=1}^n (\mu+k) P(F=k) + \sum_{k=n+1}^\infty n P(F=k)$$ where the first term on the RHS indicates that the first Tails was $\le n$, so we "start over" with $\mu$, and the second term indicates that the first $n$ flips were heads. Also note $\sum_{k=n+1}^\infty P(F=k)$ is the probability that the first $n$ flips were heads, so this equals $p^n$.

So $\mu \left( 1 - \sum_{k=1}^n P(F=k) \right) = n p^n + \sum_{k=1}^n k P(F=k) \implies \mu = p^n + \frac{1}{p^n} \sum_{k=1}^n k P(F=k).$

Finally, $\sum_{k=1}^n k P(F=k) = \sum_{k=1}^n k (1-p)p^{k-1} = \cdots = \dfrac{-n p^{n + 1} + (n + 1) p^n - 1 }{p - 1}$ after manipulating geometric series. Then, substituting into the formula above gives $\mu = \dfrac{p^{-n}(p^n-1)}{p-1}$.

• its a hitting time in a markov chain – Jorge Fernández Hidalgo Dec 28 '16 at 5:19
• Look at the 'negative binomial' distribution, which addresses your problem directly. Specifically, the Wikipedia article seems to be clearly written. – BruceET Dec 28 '16 at 5:24
• However, the negative binomial does not relate to CONSECUTIVE tosses. – UweM. Dec 28 '16 at 8:34

Let $H=1$ iffwe get $n$ consecutive heads before $n$ consecutive tails and $0$ otherwise. We can calculate $A_n=\mathbb{E}[C_n|H=1]$ by conditioning on the flip on which the process of collecting $n$ heads is interrupted by a tail. In other words, if we are interrupted on our first flip, the expected value is now $1+A_n$, if we are interrupted on our second flip, the expected value is now $2+A_n$, if..., if we are interrupted in our $n+1$th flip, the expected value is now $n$. Putting this all together, we get \begin{align} A_n&=\sum_{k=0}^{n-1}p^k(1-p)(k+1+A_n)\\ &=\sum_{k=0}^{n-1}p^k(1-p)(k+1)+\sum_{k=0}^{n-1}p^k(1-p)A_n \\ &=\frac{p^{-n}-1}{1-p} \end{align} We can do the same for $B_n=\mathbb{E}[C_n|H=0]$, except that the probabilities will be reversed. Thus we obtain $$B_n=\frac{(1-p)^{-n}-1}{p}$$ To compute $\mathbb{P}(H=1)$ we condition on whether the first flip is a head. Here, we have two possibilities, either the following $n-1$ flips are heads, or one of these $n-1$ flips results in tails, at which point we forget about all previous heads and imagine that our first flip is a tail, thus $$P=\mathbb{P}(H=1|\text{first flip is heads})=p^{n-1}+(1-p^{n-1})\mathbb{P}(H=1|\text{first flip is tails})$$ To compute $\mathbb{P}(H=1|\text{first flip is tails})$, we have two possibilities again: either the following $n-1$ flips are all tails, in which case the probability of obtaining $n$ consecutive heads before $n$ consecutive tails is zero, or somewhere along the line we get a head, in which case we start all over again as if though our first flip had been a head. Thus $$Q=\mathbb{P}(H=1|\text{first flip is tails})=(1-(1-p)^{n-1})\mathbb{P}(H=1|\text{first flip is heads})$$ We now have the simultaneous equations \begin{align} P&=p^{n-1}+(1-p^{n-1})Q \\ Q &=(1-(1-p)^{n-1})P\end{align} Which implies that $$P=\frac{p^{n-1}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$ $$Q=\frac{p^{n-1}(1-(1-p)^{n-1})}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$ Remembering we had conditioned on the first flip, we now get $$\mathbb{P}(H=1)=\frac{p^{n}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}+(1-p)p^{n-1}\frac{1-(1-p)^{n-1}}{1-(1-p^{n-1})(1-(1-p)^{n-1})}$$ Using $$\mathbb{E}[C_n]=\mathbb{E}[\mathbb{E}[C_n|H]]=A_n\mathbb{P}(H=1)+B_n(1-\mathbb{P}(H=1))$$ We obtain the desired result.

• Sorry not overly familiar with distributions but could one use the geometric distribution for this problem? – gowrath Dec 28 '16 at 5:32
• @gowrath I am afraid not, the geometric distribution is used when computing the probability that $n-1$ failures happen before a success, here we need the probability that $n$ successes happen within a given number of trials. However, the geometric distribution can be used to calculate the expected value of the negative binomial. – Guacho Perez Dec 28 '16 at 5:36
• It's $n$ consecutive H or $n$ consecutive T, not just $n$ total – user365239 Dec 28 '16 at 5:38
• Makes sense, thanks! I really need to take a stats class. – gowrath Dec 28 '16 at 5:38
• @user365239 I misread that, with first time do you mean that no tails have appeared before? – Guacho Perez Dec 28 '16 at 5:40

Suppose we use $z$ for heads and $w$ for tails. We introduce two generating functions starting with $f_1(z,w):$

$$f_1(z, w) = (1+z+z^2+\cdots+z^{n-1}) \\ \times \left(\sum_{q\ge 0} (w+w^2+\cdots+w^{n-1})^q (z+z^2+\cdots+z^{n-1})^q\right) w^n \\ = \frac{1-z^n}{1-z} \\ \times \left(\sum_{q\ge 0} w^q z^q \frac{(1-w^{n-1})^q}{(1-w)^q} \frac{(1-z^{n-1})^q}{(1-z)^q}\right) w^n \\ = w^n \frac{1-z^n}{1-z} \frac{1}{1-wz(1-w^{n-1})(1-z^{n-1})/(1-z)/(1-w)} \\ = w^n (1-w)(1-z^n) \frac{1}{(1-w)(1-z)-wz(1-w^{n-1})(1-z^{n-1})} \\ = w^n (1-w)(1-z^n) \frac{1}{1-w-z+zw^n+wz^n - w^n z^n}$$

This is the contribution from configurations ending in a sequence of $n$ tails. We get the generating function $f_2(z,w)$ for configurations ending in a sequence of heads by using the inherent symmetry and find

$$f_2(z, w) = z^n (1-z)(1-w^n) \frac{1}{1-w-z+zw^n+wz^n - w^n z^n}.$$

The desired expectation is now given by

$$\left. \frac{d}{dv}\left(f_1(pv, (1-p)v)+f_2(pv, (1-p)v)\right) \right|_{v=1}.$$

The sum is

$$\frac{w^n-w^{n+1}-w^nz^n+w^{n+1}z^n + z^n-z^{n+1}-w^nz^n+z^{n+1}w^n } {1-w-z+zw^n+wz^n - w^n z^n}.$$

The substitution yields yields for the denominator

$$D_1 = \left.1-(1-p)v-pv+ p(1-p)^nv^{n+1}+(1-p)p^nv^{n+1}-v^{2n}(1-p)^np^n\right|_{v=1} \\ = p(1-p)^n + (1-p)p^n - (1-p)^n p^n.$$

We get from the derivative

$$D_2 = -1 +(n+1)p(1-p)^n+(n+1)(1-p)p^n-2n(1-p)^np^n.$$

We get for the numerator

$$N_1 = \left.-2(1-p)^np^n v^{2n} + (1-p)^n v^n - (1-p)^{n+1} v^{n+1} + p^n v^n - p^{n+1} v^{n+1} \\ + (1-p)^{n+1} p^n v^{2n+1} + p^{n+1} (1-p)^n v^{2n+1}\right|_{v=1} \\ = -2(1-p)^n p^n + p (1-p)^n + (1-p) p^n + p^n (1-p)^n \\ = -(1-p)^n p^n + p (1-p)^n + (1-p) p^n.$$

The derivative produces

$$N_2 = -4n (1-p)^n p^n + n(1-p)^n - (n+1) (1-p)^{n+1} + np^n - (n+1)p^{n+1} + (2n+1) (1-p)^{n+1} p^n + (2n+1) p^{n+1} (1-p)^n \\ = -4n (1-p)^n p^n + n(1-p)^n - (n+1) (1-p)^{n+1} + np^n - (n+1)p^{n+1} \\ + (2n+1) (1-p)^{n} p^n \\ = -(2n-1) (1-p)^n p^n \\ + n(1-p)^n - (n+1) (1-p)^{n+1} + np^n - (n+1)p^{n+1}.$$

We seek

$$\frac{N_2}{D_1} - \frac{N_1}{D_1^2} D_2 = \frac{N_2}{D_1} - \frac{1}{D_1} D_2 = \frac{N_2-D_2}{D_1}.$$

Now $$N_2-D_2 = (1-p)^n p^n - (1-p)^n - p^n + 1.$$

Hence we have the closed form

$$\bbox[5px,border:2px solid #00A000]{ \frac{(1-p)^n p^n - (1-p)^n - p^n + 1} {p(1-p)^n + (1-p)p^n - (1-p)^n p^n}.}$$

This is also equal to

$$\frac{(1-p^n)(1-(1-p)^n)} {p(1-p) - (p-p^n)((1-p)-(1-p)^n)}$$

and hence an alternate closed form is

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{p(1-p)} \frac{(1-p^n)(1-(1-p)^n)} {1 - (1-p^{n-1})(1-(1-p)^{n-1})}.}$$

There is a Perl script which provides empirical data that approximate the closed form quite well.

#! /usr/bin/perl -w

MAIN: {
my $n = shift || 3; my$p = shift || 0.5;
my $trials = shift || 1000; my$res = 0;

for(my $tind=0;$tind < $trials;$tind++){
my ($run,$runlen, $flips) = (-1, 0, 0); while($runlen != $n){ my$HT = ( rand() < $p ? 1 : 0 ); if($HT == $run){$runlen++;
}
else{
$run =$HT;
$runlen = 1; }$flips++;
}

$res +=$flips;
}

print $res/$trials;
print "\n";

1;
}


The Maple code is used to match the data from the generating function against data produced by total enumeration and compare the closed form of the expectation to the symbolics from the generating function.

RL :=
proc(n, q)
option remember;
local ind, d, pos, cur, run, runs, gf,
zcnt, wcnt, vcnt;

gf := 0;

for ind from 2^q to 2*2^q-1 do
d := convert(ind, base, 2);

cur := -1; pos := 1;
run := []; runs := [];

while pos <= q do
if d[pos] <> cur then
if nops(run) > 0 then
runs :=
[op(runs), [run[1], nops(run)]];
fi;

cur := d[pos];
run := [cur];
else
run := [op(run), cur];
fi;

pos := pos + 1;
od;

runs := [op(runs), [run[1], nops(run)]];

zcnt := add(if(r[1] = 0, r[2], 0), r in runs);
wcnt := add(if(r[1] = 1, r[2], 0), r in runs);

if(nops(select(r->r[2] >= n, runs)) = 1) and
runs[nops(runs)][2] = n then
gf := gf + z^zcnt*w^wcnt;
fi;
od;

gf;
end;

F := (v1, v2, n) ->
v1^n*(1-v1)*(1-v2^n)
/(1-v1-v2+v1*v2^n+v2*v1^n-v1^n*v2^n);

G :=
proc(n, q)
simplify
(coeftayl(F(z*v, w*v, n) + F(w*v, z*v, n), v=0, q));
end;

X1 :=
proc(n)

subs(v=1,
diff(F(p*v, (1-p)*v, n) + F((1-p)*v, p*v, n), v));
end;

X2 :=
proc(n)
local CFD, CFN;

CFN := (1-p)^n*p^n-(1-p)^n-p^n+1;
CFD := p*(1-p)^n+(1-p)*p^n-(1-p)^n*p^n;

CFN/CFD;
end;

X3 :=
proc(n)
local CFD, CFN;

CFN := (1-p^n)*(1-(1-p)^n);
CFD := 1-(1-p^(n-1))*(1-(1-p)^(n-1));

1/p/(1-p)*CFN/CFD;
end;