# Streaks

Taking expectations and using linearity of expectation, we have

By plugging in various values for *k*, we can calculate the expected number of streaks of length *k*. If this number is large (much greater than 1), then many streaks of length *k* are expected to occur and the probability that one occurs is high. If this number is small (much less than 1), then very few streaks of length *k* are expected to occur and the probability that one occurs is low. If *k* = *c* lg *n*, for some positive constant *c*, we obtain

If *c* is large, the expected number of streaks of length *c* lg *n* is very small, and we conclude that they are unlikely to occur. On the other hand, if *c* < 1/2, then we obtain E [*X*] = Θ(1/*n*^{1/2-1}) = Θ(*n*^{1/2}), and we expect that there will be a large number of streaks of length (1/2) lg *n*. Therefore, one streak of such a length is very likely to occur. From these rough estimates alone, we can conclude that the length of the longest streak is Θ(lg *n*).