1
$\begingroup$

Flip a fair coin $n$ times, for $k>0$, find an upper bound on the probability that there is a sequence of $\log_2 n + k$ consecutive heads.

  • 2
    The easiest upper bound I can think of is $1$2012-10-07

1 Answers 1

1

There are at most $(n+1-r)2^{n-r}$ sequences with $r$ heads (there are $n+1-r$ positions for such a streak and $2^{n-r}$ possible values for the remaining flips). Therefore the probability for a sequence of $r$ heads within $n$ flips is at most $\frac{n+1-r}{2^r}$. With $r=\lceil \log_2n\rceil + k$, this is $\le \frac{n+1-\log_2n-k}{2^kn}\le2^{-k}$.

  • 0
    The result should not be surprising: With $n=2^l$ flips we expect each sequence of length $l$ approximately once, including $l$ heads. To have $l+k$ heads therefore only the $k$ flips following "the" $l$ heads sequence need to be ckeched with standard probability theory.2012-10-07