# The Expectation and the Variance of the runs

folks!
I have the following problem:
Suppose you have a coin that has chance p of landing heads. Suppose you flip the coin N times and let
X denote the number of "head runs" in N flips. A "head run" is defined as any sequence of heads.
For example the sequence HHTHHHHHTTTTHHTHT contains 4 head runs. I want to compute E(X) and Var(X).

I have a difficulty especially with variance.

Thanks.

You can consider the random variable $Y$=number of alternations (from head to tail or viceversa) in the sequence of $N$ trials. It's clear that $Y$ follows a Binomial distribution, with values in $[0,N-1]$ and $p=1/2$.

$E(Y) = (N - 1) /2$

$Var(Y) = (N - 1) /4$

The relation with $X$ takes slightly different forms depending on whether the first occurrence was a head, and whether $N$ is even or odd. This makes the problem a little cumbersome, but solvable nonetheless.

For a quick approximate (presumably quite good with $N$ moderately large) solution:

If $Y$ is odd, then: $X=(Y+1)/2$. We assume that this holds always, and then compute expectation and variance by linearity.

$E(X) \approx (N-1)/4 + 1/2 \approx N/4$

$Var(X) \approx (N-1)/16 \approx N/16$

• Thanks! Your and the reference of user1910 helped greatly.
– Martin
Oct 5, 2010 at 6:28

This question is very similar and should give some pointers.

Monte Carlo method (actually flipping the coin)

Assuming $x_i$ is the number of "head runs" in trial $i$, you can compute the sample expectation (or rather, the mean) after $n$ trials:

$$E[X]=\sum\limits_{i=0}^n x_i$$

The variance is calculated in a similar manner:

$$V[X]=E[X^2]-E[X]^2=\sum\limits_{i=0}^n x_i^2 - \left(\sum\limits_{i=0}^n x_i\right)^2$$

• this answer does not help the OP. Presumably the OP is well aware of how to find an experimental value and is asking for an exact one. Oct 4, 2010 at 16:58
• Good point, although OP doesn't specify this.
– You
Oct 4, 2010 at 17:09

Ok, i managed with Robin Chapman's help compute the following:

Let $X_1,X_2,\ldots,X_N$ be the random variables defined as follows:

$$X_i= \begin{cases} 1 \quad\text{if there is a run of heads starting at the position } i,\\ 0 \quad\text{otherwise}. \end{cases}$$ Then $X=X_1+X_2+...+X_N$. By linearity of expectation we have $E(X)=E(X_1)+\ldots+E(X_N)$.
Now, a run of heads can start at the position $i$ only by the condition "a tail at the position $i-1$". That means $P(X_i=1)=(1-p)p=qp$. But at $i=1$ there is no $i=0$, and hence $P(X_1=1)=p$. Last step: $E(X_i)=1\cdot P(X_i=1)+0\cdot P(X_i=0)=P(X_i=1)$ and finally: $$E(X)=p+(N-1)pq$$

In case of $p=1/2$ we have $E(X)=(N+1)/4$, and if $N=>\infty$ then $E(X)=>N/4$.

Congrats leonbloy! Your approach was very fruitful. Now, to get exact variance seems to be rather tricky. But in any case, many thanks anyway.