Suppose you flip a fair coin n times. What is the longest streak of consecutive heads that you expect to see? The answer is Θ(lg n), as the following analysis shows.

We first prove that the expected length of the longest streak of heads is O(lg n). The probability that each coin flip is a head is 1/2. Let Aik be the event that a streak of heads of length at least k begins with the ith coin flip or, more precisely, the event that the k consecutive coin flips i, i 1, ..., i k - 1 yield only heads, where 1 ≤ kn and 1 ≤ in -k 1. Since coin flips are mutually independent, for any given event Aik, the probability that all k flips are heads is