Lesson 5

Problem. Test your intuition.

Let \(N\) be the total number of objects (also called the population size). We independently select an object \(n\) times uniformly at random and with replacement (from all \(N\) objects) and check how many of them have the property we need. Let \(\alpha\) be a random variable equal to this count. We want to achieve the following guarantee: \[\Pr\left[\left|\frac{\alpha}{n}-p\right| \le 0.04\right] \ge 0.95 \ .\] How large (approximately) should \(n\) be for this?