3
$\begingroup$

What is the expected number of strings of exactly k consecutive heads if a fair coin is tossed n times?

My current answer is $$ {n-1\choose k} (\frac{1}{2})^{(k-1)} $$

Is this correct?

A possible string : HTHHHTHH. This has 3 strings for 2 consecutive heads. The string for 3 Hs, is also 2 strings for 2 consecutive Hs.

$\endgroup$
  • $\begingroup$ How did you get this result ? If you toss a coin 5 times, how many strings with the length of k=3 are possible ? $\endgroup$ – callculus Oct 16 '14 at 18:39
  • $\begingroup$ 4 choose 3 locations possible, each with (1/2)^(k-1) probability of being the kth Head in the string $\endgroup$ – mathguy Oct 16 '14 at 18:42
  • $\begingroup$ I have only 3. $hhhtt-thhht-tthhh$ The formula would be $n-k+1$ for the first part. $\endgroup$ – callculus Oct 16 '14 at 18:45
  • $\begingroup$ I should give a possible string, HTHHHTHH. This has 3 strings for 2 consecutive heads. The string for 3 Hs, is also 2 strings for 2 consecutive Hs. $\endgroup$ – mathguy Oct 16 '14 at 18:48
  • 1
    $\begingroup$ The formula for the current answer, ${n-1\choose k}(1/2)^{(k-1)}$, is clearly wrong when $k=1$. $\endgroup$ – Barry Cipra Oct 16 '14 at 19:06
3
$\begingroup$

The probability of tossing $k$ consecutive heads in $k$ tosses is simply $(1/2)^k$. There are $n-k+1$ possible starting positions (if we start counting after the $n-k+1$th toss, we do not have enough tosses for $k$ consecutive heads). Thus, the expected number is simply $\frac{n-k+1}{2^k}$.

Edit: To make this clearer, for $i = 1, \dots, n-k+1$, let $X_i$ be an indicator function such that $X_i = 1$ if there are $k$ consecutive heads starting at position $i$ and $0$ otherwise. Then $P(X_i = 1) = 1/2^k$. The total number $T$ of $k$ consecutive heads is $$T = X_1 + \dots + X_{n-k+1}.$$ Thus, $E[T] = (n-k+1)E[X_1] = \frac{n-k+1}{2^k}.$

$\endgroup$
  • $\begingroup$ I should give a possible string, HTHHHTHH. This has 3 strings for 2 consecutive heads $\endgroup$ – mathguy Oct 16 '14 at 18:45
  • $\begingroup$ Yes, see the edit. $\endgroup$ – snar Oct 16 '14 at 18:58
  • 2
    $\begingroup$ Important to note: Of course $X_i$ and $X_{i+1}$ are not independent, but as long as we are only concerned with the expected value, we couldn't care less. The exact distribution for $T$ is apparently more complicated. $\endgroup$ – Hagen von Eitzen Jan 17 '17 at 7:25

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.