 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/discrete-mathematics-continuous-mathematics-and-probability/9/c/ii/solution

The normalized sum has mean one and variance

(5 n - 2) / n^{2}

. For every fixed

ϵ > 0

0 \leq P (\frac{S _{n}}{n} > 1 + ϵ) \leq P (\frac{S _{n}}{n} - 1 > ϵ) \leq \frac{5 n - 2}{n ^{2} ϵ ^{2}} ⟶ 0.

This proves the requested limit, and in fact proves convergence in probability of

S_{n} / n

to one. It is a finite covariance range weak law: adjacent dependence is harmless here because only linearly many covariance terms survive.

 New to topics? Read the docs here!