Lesson 3

To answer this question, we need to compute the variance of \(\alpha\): \[\begin{align*}\operatorname{Var}[\alpha]&=\operatorname{Var}\left[\beta/n\right]=\\&=\frac{1}{n^2}\cdot \operatorname{Var}[\beta]=\\&=\frac{1}{n^2}\cdot n \cdot \frac{1}{4}=\\&=\frac{1}{4n}\ .\end{align*}\] Then, by Chebyshev's inequality, for any \(\varepsilon>0\) we have \[\Pr\left[\left|\alpha-\frac{1}{2}\right| \ge \varepsilon \right] \le \frac{\operatorname{Var}[\alpha]}{\varepsilon^2}= \frac{1}{4n\varepsilon^2}\ .\] Substituting \(\varepsilon=1/4\), we get \[\Pr\left[\left|\alpha-\frac{1}{2}\right| \ge \frac{1}{4} \right] \le \frac{4}{n}\ .\]

As expected, as \(n\) increases, this probability decreases. But we will see below that it decreases much faster!