 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/b/8/b/iii/solution

Now

ω (n) \to - \infty

makes

E X = 2^{- ω (n)} \to \infty

P (X = 0) \leq \frac{Var X}{( E X ) ^{2}} \leq \frac{3}{E X} ⟶ 0.

For every fixed

ϵ > 0

, they likewise give

P (\frac{X}{E X} - 1 > ϵ) \leq \frac{3}{ϵ ^{2} E X} ⟶ 0 .

Thus the count is concentrated about its growing mean, despite the overlapping runs.

 New to topics? Read the docs here!