# 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 '14 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. – drhab Apr 26 '14 at 18:43