State the first and second Borel-Cantelli Lemmas and the Kolmogorov 0-1 law.

Let $\left(X_{n}\right)_{n \geqslant 1}$ be a sequence of independent random variables with distribution given

by

$$\mathbb{P}\left(X_{n}=n\right)=\frac{1}{n}=1-\mathbb{P}\left(X_{n}=0\right)$$

and set $S_{n}=\sum_{i=1}^{n} X_{i}$.

(a) Show that there exist constants $0 \leqslant c_{1} \leqslant c_{2} \leqslant \infty$ such that $\lim \inf _{n}\left(S_{n} / n\right)=c_{1}$, almost surely and $\lim \sup _{n}\left(S_{n} / n\right)=c_{2}$ almost surely.

(b) Let $Y_{k}=\sum_{i=k+1}^{2 k} X_{i}$ and $\tilde{Y}_{k}=\sum_{i=1}^{k} Z_{i}^{(k)}$, where $\left(Z_{i}^{(k)}\right)_{i=1}^{k}$ are independent with

$$\mathbb{P}\left(Z_{i}^{(k)}=k\right)=\frac{1}{2 k}=1-\mathbb{P}\left(Z_{i}^{(k)}=0\right), \quad 1 \leqslant i \leqslant k,$$

and suppose that $\alpha \in \mathbb{Z}^{+}$.

Use the fact that $\mathbb{P}\left(Y_{k} \geqslant \alpha k\right) \geqslant \mathbb{P}\left(\tilde{Y}_{k} \geqslant \alpha k\right)$ to show that there exists $p_{\alpha}>0$ such that $\mathbb{P}\left(Y_{k} \geqslant \alpha k\right) \geqslant p_{\alpha}$ for all sufficiently large $k$.

[You may use the Poisson approximation to the binomial distribution without proof.]

By considering a suitable subsequence of $\left(Y_{k}\right)$, or otherwise, show that $c_{2}=\infty$.

(c) Show that $c_{1} \leqslant 1$. Consider an appropriately chosen sequence of random times $T_{i}$, with $2 T_{i} \leqslant T_{i+1}$, for which $\left(S_{T_{i}} / T_{i}\right) \leqslant 3 c_{1} / 2$. Using the fact that the random variables $\left(Y_{T_{i}}\right)$ are independent, and by considering the events $\left\{Y_{T_{i}}=0\right\}$, or otherwise, show that $c_{1}=0$.