# Flip a fair coin n times

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.

-
The easiest upper bound I can think of is $1$ – Ross Millikan Oct 7 '12 at 16:36

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}$.
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. – Hagen von Eitzen Oct 7 '12 at 16:56