Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
The easiest upper bound I can think of is $1$ –  Ross Millikan Oct 7 '12 at 16:36

1 Answer 1

up vote 1 down vote accepted

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}$.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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