# Expected number of runs in a sequence of coin flips

A coin with heads probability $p$ is flipped $n$ times. A "run" is a maximal sequence of consecutive flips that are all the same. For example, the sequence HTHHHTTH with $n=8$ has five runs, namely H, T, HHH, TT,H. Show that the expected number of runs is $$1+2(n-1)p(1-p).$$

I have tried to use some generating function on this but calculus got pretty messy and didn't work.

I'd use indicator random variables. For $1\leq j\leq n-1$, let $Z_j$ take the value $1$ if the $j$th and $j+1$st coin tosses are different, and take the value $0$ otherwise. Then the number of runs is $R=1+\sum_{j=1}^{n-1}Z_j$ and its expected value is $$\mathbb{E}(R)=1+ \sum_{j=1}^{n-1}\, \mathbb{E}(Z_j)=1+(n-1) 2p(1-p).$$ I will leave the calculation $\mathbb{E}(Z_j)=2p(1-p)$ as an exercise!

Using indicator random variable is a good way to solve this question (see the solution above). What's more, we can calculate the variance of the number of runs:$$Var\left( R \right) =Var\left( \sum _{ j=1 }^{ n-1 }{ { Z }_{ j } } \right) =E\left\{ { \left( \sum _{ j=1 }^{ n-1 }{ { Z }_{ j } } \right) }^{ 2 } \right\} -{ E\left( \sum _{ j=1 }^{ n-1 }{ { Z }_{ j } } \right) }^{ 2 }$$ $Z_j$ is a Bernoulli distribution, $Z_j$ and $Z_k$ are independent if $\left| j-k \right| \ge 2$(notice that $Z_j$ and $Z_{j+1}$ are dependent).

We can get $Var\left( R \right)=2pq\left( 2n-3-2pq\left( 3n-5 \right) \right)$.

• hi sir, I don't understand the last step, can you elaborate on how you get $Var(R)$? Oct 15, 2019 at 21:46
• @user614287 what liuliu is pointing out with the hint is that we need to take into account the Covariance for consecutive flips in the run. Using symmetry you can reduce his equation to something like this, $(n-1)*Var(Z_j) + 2*(n-2)* Cov(Z_j,Z_k)$
– Otis
Apr 14 at 3:03

We already have 2 good solutions here, but wanted to answer using the conventional approach.

Let $\mathbb E(k)$ be expected number of runs in a series of $k$ coin tosses. It is important to remember that the coin tosses are memoryless. Therefore, $\mathbb E(k+1)$ depends only on the value of coin toss $k$ and $k+1$. The value of $\mathbb E(k+1)$ will increase by 1 if $k^{th}$ and $k+1^{th}$ tosses are different.

Keeping this in mind, we translate these into equations

$$\mathbb E(k+1) = p(p\mathbb E(k) + (1-p)(1+ \mathbb E(k)) + (1-p)((1-p)\mathbb E(k) + p(1+ \mathbb E(k)))$$

Rearranging this a bit gives us

$$\mathbb E(k+1) = 2p(1-p) + \mathbb E(k)$$

Our $\mathbb E(k)$ is of the form $\mathbb E(k) = Ck +D$ for some constant $C$ and $D$. The result follows after finding these constants from the previous equation and the initial condition.