Probability – Expected Number of Runs in a Sequence of Coin Flips

discrete mathematicsprobability

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.

Best Answer

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!

Related Question