Lesson 3

Optional Problems.

1. (20 points) A fair coin is tossed \(160\) times. Let \(p\) be the probability \(p = \Pr[\text{at least }120 \text{ heads}]\). Compute \(p\) (numerically) and give upper bounds derived from Markov, Chebyshev, and Chernoff inequalities.
2. (20 points) Show that the proportion of empty bins tends to \(1/e\) as \(n\to\infty\) when \(n\) balls are thrown uniformly into \(n\) bins.
   Hint:

   Let \(X\) denote the number of empty bins. Recall that convergence "in probability" for the proportion \(X/n\) requires showing that the probability of deviation from the mean goes to zero. Calculate the variance of \(X\) by considering the covariance between indicator variables for different bins.
3. (20 points) Suppose you have an algorithm \(A\) that estimates a value \(\mu\) such that the output \(Y\) of \(A\) satisfies \[\Pr[|Y - \mu| > \varepsilon] < \frac{1}{3}.\] We want a stronger guarantee: a probability of failure at most \(\delta\) (where \(\delta \ll 1/3\)). Construct an algorithm \(A'\) with such guarantee such that the running time of \(A'\) is at most \(O(\log(1/\delta))\) times bigger than the time complexity of \(A\).