1
$\begingroup$

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)

$\endgroup$

3 Answers 3

3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Very clear solution! $\endgroup$
    – charmd
    Nov 28, 2020 at 6:48
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – charmd
    Nov 28, 2020 at 6:48
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.