# variance of the number of coin toss to get N heads in row

The expected value of the number of coin toss to get N heads in a row is discussed here: How many flips of a fair coin does it take until you get N heads in a row?

How can we find the variance?

The underlying stochastic recursion might help.

Let $X_N$ denote the number of tosses needed to get $N$ heads in a row. At the time when one first gets $N$ heads in a row, either one gets a new head, and this yields $N+1$ heads in a row, or one gets a tail and then everything starts anew. Thus, for every $N\geqslant0$, one gets the key-identity $$\color{red}{X_{N+1}=X_N+1+B\bar X_{N+1},\quad B\sim\text{Bernoulli},\quad \bar X_{N+1}\sim X_{N+1}},$$ where $(B,\bar X_{N+1},X_N)$ is independent, $P(B=0)=P(B=1)=\frac12$, $\bar X_{N+1}$ is distributed like $X_{N+1}$, and the correct initialization is $\color{red}{X_0=0}$.

This stochastic recursion fully encodes the distribution of every $X_N$ and it allows to compute recursively their characteristics.

1. Expectations Taking expectations of both sides of the key-identity, one gets $$E(X_{N+1})=E(X_N)+1+\tfrac12E(X_{N+1}),$$ hence $$E(X_{N+1})=2E(X_N)+2.$$ This is solved easily since $$E(X_{N+1})+2=2(E(X_N)+2),$$ hence $$E(X_N)=2^{N}(E(X_0)+2)-2=2\cdot(2^N-1).$$

2. Variances The same representation yields the variances since $$X_{N+1}-E(X_{N+1})=X_N-E(X_N)+B\bar X_{N+1}-\tfrac12E(X_{N+1}),$$ hence $$\mathrm{var}(X_{N+1})=\mathrm{var}(X_N)+E(Z_N),$$ where $$Z_N=B\bar X_{N+1}^2-BE(X_{N+1})\bar X_{N+1}+\tfrac14E(X_{N+1})^2,$$ hence $$E(Z_N)=\tfrac12E(X_{N+1}^2)-\tfrac12E(X_{N+1})^2+\tfrac14E(X_{N+1})^2,$$ and $$\mathrm{var}(X_{N+1})=2\mathrm{var}(X_N)+\tfrac12E(X_{N+1})^2,$$ from which (I believe that) one gets (something similar to) $$\mathrm{var}(X_N)=2\cdot(2\cdot2^{2N}-2N\cdot2^N-1).$$ 3. Full distributions The key-identity also yields the full distribution of every $X_N$ since, for every $|s|\leqslant1$, $$E(s^{X_{N+1}})=E(s^{X_N})\cdot s\cdot E(s^{B\bar X_{N+1}}),$$ that is, $$E(s^{X_{N+1}})=E(s^{X_N})\cdot s\cdot \tfrac12(1+E(s^{X_{N+1}})),$$ hence $$E(s^{X_{N+1}})=\frac{s\cdot E(s^{X_N})}{2-s\cdot E(s^{X_N})}.$$ This can be rewritten as $$\frac1{E(s^{X_{N+1}})}-\frac{s}{2-s}=\frac2s\left(\frac1{E(s^{X_{N}})}-\frac{s}{2-s}\right).$$ Furthermore, $E(s^{X_0})=1$. Finally, $$E(s^{X_N})=\frac{(2-s)s^N}{2^{N+1}(1-s)+s^{N+1}}.$$ From this point, it is relatively straightforward to show that, for every $t\geqslant0$, $$\lim_{N\to\infty}E(\mathrm e^{-tX_N/2^N})=\frac1{1+2t},$$ which shows that $2^{-N}X_N$ converges in distribution to an exponential random variable of parameter $\frac12$, in symbols, $$\color{red}{\frac{X_N}{2^N}\stackrel{\text{dist.}}{\longrightarrow}2\cdot\Xi},\qquad\color{red}{\Xi\sim\mathcal E(1)}.$$ And, to fully complete this circle of ideas, note that $\Theta=2\cdot\Xi$ solves the identity $$\Theta\stackrel{\text{dist.}}{=}\tfrac12\cdot\Theta+B\cdot\bar\Theta,$$ with the obvious notations, and that the nondegenerate solutions of this identity are the exponential distributions.

At the moment I am not in the opportunity to provide a complete answer. But I suggest to look in the following direction:

Let $T$ stand for the number of tosses needed to arrive at the first tail, and let $X$ stand for the number of tosses needed to arrive at $N$ heads on a row.

$\mathbb{E}X$ is allready known from answers on the question you quoted , so to find $\text{Var}X=\mathbb{E}X^{2}-\left(\mathbb{E}X\right)^{2}$ it is enough to find $\mathbb{E}X^{2}$.

$$\mathbb{E}X^{2}=\sum_{i=1}^{N}\mathbb{E}\left(X^{2}\mid T=i\right)P\left(T=i\right)+\mathbb{E}\left(X^{2}\mid T>N\right)P\left(T>N\right)$$ $$=\sum_{i=1}^{N}\mathbb{E}\left(i+X\right)^{2}2^{-i}+N^{2}2^{-N}$$

Making use of the expression for $\mathbb{E}X$ this allows you to find an expression for $\mathbb{E}X^2$.

• This seems like a pretty complete answer to me. What, the computations needed to finish it? Not really a problem...
– Did
Apr 26, 2014 at 18:31
• To confess: I am just too lazy for that at the time. Next to that it is off course a good thing for the OP to do some work as well. Apr 26, 2014 at 18:43
• I feel like your answer is very good but I still don't understand why $$\mathbb{E}\left(X^{2}\mid T=i\right) = \mathbb{E}\left(i+X\right)^{2}$$ and why $$\mathbb{E}\left(X^{2}\mid T>N\right) = N^{2}$$ I would really appreciate some feedback. Jul 27, 2020 at 21:58
• @Guess601 Under condition $T=i\leq N$ we come in a position that things start over again. This with $i$ tosses in our pocket that yielded no result. That means that the distribution of $X$ under condition $T=i$ is the same as the distribution of $i+X$:$$(X\mid T=i)\stackrel{d}{=}i+X$$Under condition $T>N$ we are in the situation that the first $N$ tosses must have been heads so that $X$ must have taken value $N$:$$(X\mid T>N)\stackrel{d}{=}N$$where $N$ denotes a constant. Jul 28, 2020 at 12:10

I have decided to place a second and complete answer. This also to have a reference point if sortlike questions show up.

Expectation

Let $$T$$ stand for the number of tosses needed to arrive at the first tail, and let $$X$$ stand for the number of tosses needed to arrive at $$N$$ heads on a row.

To make things more general let $$p$$ denote the probability on heads.

Then $$T$$ has geometric distribution with $$P\left(T=k\right)=p^{k-1}q$$ for positive integer $$k$$.

Now observe that:

$$\mathbb{E}\left[X\mid T=k\right]=\begin{cases} \mu+k & \text{if }k\leq N\\ N & \text{otherwise} \end{cases}$$

This tells us that:$$\mathbb{E}\left[X\mid T\right]=\begin{cases} \mu+T & \text{if }T\leq N\\ N & \text{otherwise} \end{cases}$$

We can also write this equality as:$$\mathbb{E}\left[X\mid T\right]=\mu\left(1-\mathbf{1}_{T>N}\right)+\sum_{k=0}^{N-1}\mathbf{1}_{T>k}$$

Taking expectation on both sides we arrive at:$$\mu=\mu\left(1-P\left(T>N\right)\right)+\sum_{k=0}^{N-1}P\left(T>k\right)$$ or equivalently: $$\mu=\mu\left(1-p^{N}\right)=\sum_{k=0}^{N-1}p^{k}$$ Eventually we find:$$\mu=\sum_{k=1}^{N}p^{-k}=\frac{1-p^{N}}{p^{N}\left(1-p\right)}\tag1$$

Variance.

Now an effort to find $$\sigma^{2}:=\mathsf{Var}X$$.

We will practicize the rule:$$\mathsf{Var}X=\mathsf{Var}\left(\mathbb{E}\left[X\mid T\right]\right)+\mathbb{E}\left(\mathsf{Var}\left[X\mid T\right]\right)$$

Observe that for $$k\leq N$$ we have $$\left(X\mid T=k\right)\stackrel{d}{=}k+X$$ so that in that case: $$\mathsf{Var}\left[X\mid T=k\right]=\mathsf{Var}\left(k+X\right)=\mathsf{Var}X=\sigma^{2}$$ For $$k>N$$ we find that $$\left(X\mid T=k\right)$$ is degenerated so that in that case $$\mathsf{Var}\left[X\mid T=k\right]=0$$.

This can be summarized as:$$\mathsf{Var}\left[X\mid T\right]=\sigma^{2}\left(1-\mathbf{1}_{Z>N}\right)$$

making clear that: $$\mathbb{E}\left(\mathsf{Var}\left[X\mid T\right]\right)=\sigma^{2}\left(1-p^{N}\right)$$

Substituting we then find: $$\sigma^{2}=\mathsf{Var}\left(\mathbb{E}\left[X\mid T\right]\right)+\sigma^{2}\left(1-p^{N}\right)$$ or equivalently: $$p^{N}\sigma^{2}=\mathsf{Var}\left(\mathbb{E}\left[X\mid T\right]\right)$$

We already found that: $$\mathbb{E}\left[X\mid T\right]-\mu=\sum_{k=0}^{N-1}\mathbf{1}_{T>k}-\mu\mathbf{1}_{T>N}$$

So finding $$\mathsf{Var}\left(\mathbb{E}\left[X\mid T\right]\right)$$ comes to finding $$\mathbb{E}\left[\left(\sum_{k=0}^{N-1}\mathbf{1}_{T>k}-\mu\mathbf{1}_{T>N}\right)^{2}\right]$$.

Here

\begin{aligned}\left(\sum_{k=0}^{N-1}\mathbf{1}_{T>k}-\mu\mathbf{1}_{T>N}\right)^{2} & =\sum_{i=0}^{N-1}\sum_{j=0}^{N-1}\mathbf{1}_{T>i}\mathbf{1}_{T>j}-2\mu\sum_{k=0}^{N-1}\mathbf{1}_{T>k}\mathbf{1}_{T>N}+\mu^{2}\mathbf{1}_{T>N}\\ & =\sum_{i=0}^{N-1}\sum_{j=0}^{N-1}\mathbf{1}_{T>\max\left(i,j\right)}-2\mu\sum_{k=0}^{N-1}\mathbf{1}_{T>N}+\mu^{2}\mathbf{1}_{T>N} \end{aligned}

and taking the expectation we find at first hand: $$\mathsf{Var}\left(\mathbb{E}\left[X\mid T\right]\right)=\sum_{k=0}^{N-1}\left(2k+1\right)p^{k}-2N\mu p^{N}+\mu^{2}p^{N}$$

and consequently: $$\sigma^{2}=p^{-N}\sum_{k=0}^{N-1}\left(2k+1\right)p^{k}-2N\mu+\mu^{2}$$

After finding a closed form for $$\sum_{k=0}^{N-1}\left(2k+1\right)p^{k}$$ and substituting $$(1)$$ we finally arrive at:

$$\sigma^{2}=\frac{1-p^{2N+1}-\left(2N+1\right)p^{N}\left(1-p\right)}{p^{2N}\left(1-p\right)^{2}}\tag2$$

Substituting $$p=\frac12$$ we find: $$2^{2+2N}-2-N2^{2+N}-2^{1+N}$$ which differs from what Did says about this in his (beautiful!) answer. Also he spoke words as "I believe that" and "something similar to" already pointing at some level of uncertainty. Only my last term is missing in Dids answer.

If we apply a sanity check for $$N=1$$ then the variance must be equalize the variance of geometric distribution with parameter $$p=2$$ which is $$2$$.

My answer passes this test, but the answer of Did does not.