Streaks

As an example, for n = 1000 coin flips, the probability of having a streak of at least 2 ⌈lg n⌉= 20 heads is at most 1/n = 1/1000. The chances of having a streak longer than 3 ⌈lg n⌉= 30 heads is at most 1/n² = 1/1,000,000.

We now prove a complementary lower bound: the expected length of the longest streak of heads in n coin flips is Ω(lg n). To prove this bound, we look for streaks of length s by partitioning the n flips into approximately n/s groups of s flips each. If we choose s = ⌊(lg n)/2⌋, we can show that it is likely that at least one of these groups comes up all heads, and hence it is likely that the longest streak has length at least s = Ω(lg n). We will then show that the longest streak has expected length Ω(lg n).

We partition the n coin flips into at least ⌊n/ ⌊(lg n)/2⌋⌋groups of ⌊(lg n)/2⌋consecutive flips, and we bound the probability that no group comes up all heads. By equation (5.9), the probability that the group starting in position i comes up all heads is

The probability that a streak of heads of length at least ⌊(lg n)/2⌋does not begin in position i is therefore at most . Since the ⌊n/ ⌊(lg n)/2⌋⌋groups are formed from mutually exclusive, independent coin flips, the probability that every one of these groups fails to be a streak of length ⌊(lg n)/2⌋is at most

For this argument, we used inequality (3.11), 1 x ≤ e^x , and the fact, which you might want to verify, that for sufficiently large n.

Thus, the probability that the longest streak exceeds ⌊(lg n)/2⌋ is

We can now calculate a lower bound on the expected length of the longest streak, beginning with equation (5.11) and proceeding in a manner similar to our analysis of the upper bound:

As with the birthday paradox, we can obtain a simpler but approximate analysis using indicator random variables. We let X_ik = I{A_ik} be the indicator random variable associated with a streak of heads of length at least k beginning with the ith coin flip. To count the total number of such streaks, we define