1 Robust Mean Estimation via Concentration Inequalities Suppose we observe a sequence of i.i.d. random variables X1, . . . , X\". Their distribution is unknown, and has unknown mean u and known variance 02. In this question, we will investigate two different estimators for the mean u: the sample mean, and the sqcalled \"median of means\" estimator. In particular, we will analyze them in terms of how many samples n are required to estimate it to a given precision e and for a condence threshold 6. We'll start with the sample mean for parts (a) (c): in other words, we'll use X1, . . . , X.n to compute an estimate 3,, = % 21X,- for the mean H- We want to see what sample size it guarantees that lP(| ,u| 2 e) S 6. Hint: for this problem, you might nd it useful to watch the walkthrough of Discussion 9, question 2. 2 (a) (2 points) Let S1, = imix, Use Chebyshev's inequality to show that n = 312 samples are suicient for |Sn ul 5 6 with probability at least 1 6. (b) (3 points) Now assume that each X,- is bounded between a and b. Use Hoeding's inequality to compute the number of samples n sufcient for |Sn ,u| S e with proba bility at least 1 6. In particular, show that the dependence of n on 6 is O(log(1/6))