# 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 '10 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. – Qiaochu Yuan Oct 4 '10 at 16:58
Good point, although OP doesn't specify this. – You Oct 4 '10 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.

-