Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.