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/n2 = 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
Pr {Ai,⌊(lg n)/⌋} |
= |
1/2⌊(lgn)/⌋ |
|
≥ |
.1/ √n |
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 ≤ ex , 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 Xik = I{Aik} 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