Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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!

share|improve this answer

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

share|improve this answer

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.