Lesson 6

Recall that \(\alpha\) follows a binomial distribution: \(\alpha=\chi_{1}+\dotsb+\chi_{n}\), where \[\chi_{i}=[\text{\(i\)-th object has the required property}] \ .\] Then \[\begin{align*}\operatorname{Var}[\alpha]&=\operatorname{Var}[\chi_{1}+\dotsb+\chi_{n}]=\\&=\operatorname{Var}[\chi_{1}]+\dotsb+\operatorname{Var}[\chi_{n}]=\\&=n(p(1-p)) \le \\&\le n \cdot \frac{1}{4} = \frac{n}{4} \ .\end{align*}\] Thus, \[\operatorname{Var}\left[\frac{\alpha}{n}\right]=\frac{\operatorname{Var}[\alpha]}{n^2}\le \frac{1}{4n}\ .\] By Chebyshev's inequality \[\Pr\left[\left|\frac{\alpha}{n}-p\right| \ge 0.04\right] \le \frac{\operatorname{Var}\left[\frac{\alpha}{n}\right]}{(0.04)^2}\le \frac{1}{4n(0.04)^2}=\frac{156.25}{n}\ .\] To ensure this value is at most \(0.05\), it is sufficient to take \(n \ge 3\ 125\).