Lesson 2

Theorem (law of large numbers). Let \(\alpha_{1}, \alpha_{2}, \dotsc\) be an infinite sequence of pairwise independent random variables with expectation \(e\) and variance \(d\), and let \(\beta_{n}\) be the mean of the first \(n\) variables: \[\beta_{n}=\frac{\alpha_1+\dotsb+\alpha_n}{n}\ .\] Then, for large \(n\), the value of \(\beta_{n}\) is close to \(e\) with probability close to one: for any constant \(\varepsilon>0\), \[\lim_{n \to \infty}\Pr[|\beta_{n} - e| < \varepsilon] = 1 \ .\]

Proof. Indeed, \[\begin{align*}\operatorname{E}[\beta_{n}]&=\operatorname{E}\left[\frac{1}{n}\cdot(\alpha_{1}+\dotsb+\alpha_{n})\right] =\\&=\frac{1}{n}\cdot \operatorname{E}[\alpha_{1}+\dotsb+\alpha_{n}]=&\text{(linearity)}\\&=\frac{1}{n} \cdot (\operatorname{E}[\alpha_{1}]+\dotsb+\operatorname{E}[\alpha_{n}])=\\&=\frac{1}{n} \cdot ne=e \ ,\end{align*}\] \[\begin{align*}\operatorname{Var}[\beta_{n}]&= \operatorname{Var}\left[\frac{1}{n}\cdot(\alpha_{1}+\dotsb+\alpha_{n})\right]=\\&=\frac{1}{n^2}\operatorname{Var}[\alpha_{1}+\dotsb+\alpha_{n}]=&\text{(independence)}\\&=\frac{1}{n^2}(\operatorname{Var}[\alpha_{1}]+\dotsb+\operatorname{Var}[\alpha_{n}])=\\&=\frac{d}{n}\ .\end{align*}\] Then, by Chebyshev's inequality, the following inequality holds: \[\Pr[|\beta_{n}-e| \ge \varepsilon]=\Pr[|\beta_{n}-\operatorname{E}[\beta_{n}]| \ge \varepsilon] \le \frac{\operatorname{Var}[\beta_n]}{\varepsilon^2}=\frac{d}{n\varepsilon^2}\ .\]◼