What is the expected number of times to see k consecutive heads in n coin tosses?

Question

For example, if k = 2, and you have the sequence HHH, then you've seen k consecutive heads twice.

Answer 1

In $n$ coin tosses, there are $n-k+1$ blocks of $k$ consecutive coin tosses. Each block has a $2^{-k}$ probability of being all heads. Now use linearity of expectation to get your answer.

Answer 2

For $i=1$ to $n-k+1$, let $X_i=1$ if there are $k$ consecutive heads starting at $i$, and let $X_i=0$ otherwise. Then the number of occurrences of $k$ consecutive heads is $\sum_1^{n-k+1}X_i$.

By the linearity of expectation, the expectation of this is $\sum_1^{n-k+1}E(X_i)$.

Each $X_i$ has expectation $\frac{1}{2^k}$. So our expectation is $\frac{n-k+1}{2^k}$.

Remark: One might imagine finding the mean number of times by first finding the distribution of the random variable $T$ that counts the number of sequences of $k$ consecutive heads. However, that distribution is painful to describe. The method of Indicator Random Variables bypasses finding the distribution. With some care, it can also be used to find the variance of $T$.

Answer 3

Label the successive tosses $X_1, X_2,.... X_n$. So for example, in the sequence HTH we have $X_1= H, X_2= T, X_3 = H$.

Let $I_l$ be an indicator taking the value 1 if the sequence starting at position $l$ is k consecutive heads. For example, in the sequence $HTHHTH$, with $k=2$ we have $I_1 = 0, I_2 = 0, I_3 = 1, I_4 = 0, I_5 = 0$. Then, $$P(I_l = 1) = \frac{1}{2^k}$$ and $$P(I_l= 0) = 1-\frac{1}{2^k}$$ This has expected value $$E(I_l) = \frac{1}{2^k}$$ Now, define the sum of them to be $$S = \sum_{l=1}^{n-k+1} I_l$$ Then, the expected number of times to see k consecutive heads is $$E(S) = E(\sum_{l=1}^{n-k} I_l) = \sum_{l=1}^{n-k} E(I_l) = \frac{n-k+1}{2^k}$$