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

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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.