Lesson 4

We have just proven that \[\Pr\left[\left|\alpha-\frac{1}{2}\right| \ge \frac{1}{4} \right] \le \frac{4}{n}\ .\] For example, for \(n=60\), we obtain the upper bound \(4/60 \approx 0.0667\).

Problem. To understand how accurate this estimate is for \(n=60\), compute this probability exactly: \[\Pr\left[\left|\alpha-\frac{1}{2}\right| \ge \frac{1}{4} \right] = \frac{1}{2^n}\cdot\left(\binom{n}{0}+\dotsb+\binom{n}{n/4}+\binom{n}{3n/4}+\dotsb+\binom{n}{n}\right) \ .\]