# Average number of head streaks in $N$ coin tosses

You throw $$N$$ times a fair coin. What is the expected number of subsequences of $$k$$ consecutive heads?

For instance, with $$N=6$$ and $$k=2$$, for the outcome HTHHHH, we would get $$3$$ such subsequences.

I know the solutions to two related problems, but did not find this one being asked:

• what is the expected number $$N$$ needed to get $$k$$ consecutive heads when throwing coins (see here)

• what is the probability of having at least $$k$$ consecutive heads for $$N$$ throws (see here)

For $$j = 1,\ldots,n$$, let $$X_j = 0$$ if the $$j$$-th coin flip is tails and $$X_j = 1$$ if the $$j$$-th coin flip is heads. The number of subsequences of $$k$$ consecutive heads is $$N = \sum_{j = 0}^{n-k}X_{j+1}X_{j+2}\cdots X_{j+k}.$$ Do you see why this is true? Now, using linearity of expectation followed by the fact that $$X_1,\ldots,X_n$$ are independent, we have \begin{align*} E[N] &= E\left[\sum_{j = 0}^{n-k}X_{j+1}X_{j+2}\cdots X_{j+k}\right] \\ &= \sum_{j = 0}^{n-k}E[X_{j+1}X_{j+2}\cdots X_{j+k}] \\ &= \sum_{j = 0}^{n-k}E[X_{j+1}]E[X_{j+2}] \cdots E[X_{j+k}]. \end{align*}

Can you finish the problem from here?

• Very clear solution! Nov 28, 2020 at 6:48

The number of possible sub-sequences is (n-k+1). Multiply these by the probability for each, p = (.5)^k. So, for n=6, k=2, E [k consecutive heads] = (6-2+1)(.25) = 1.25.

• I agree that "the number of possible sub-sequences [can be counted as] $n-k+1$", but I am not sure what argument you are thinking of when writing this Nov 28, 2020 at 6:48

All head streaks either end $$\ldots HT$$ or are at the far end ending $$\ldots H$$ and all such cases are head streaks

The expected number of times $$TH$$ appears is $$\frac{n-1}{4}$$ and the probability the final throw is an $$H$$ is $$\frac12$$

So add these together to get $$\dfrac{n+1}{4}$$ expected head streaks