Problem:

Suppose we want to estimate the mean µ of a random variable $ X$ from a sample $ X_1 , \dots , X_N$ drawn independently from the distribution of $ X$ . We want an $ \varepsilon$ -accurate estimate, i.e. one that falls in the interval $ (\mu − \varepsilon, \mu + \varepsilon)$ .

Show that a sample of size $ N = O( \log (\delta^{−1} )\, \sigma^2 / \varepsilon^2 )$ is sufficient to compute an $ \varepsilon$ -accurate estimate with probability at least $ 1 −\delta$ .

Hint: Use the median of $ O(log(\delta^{−1}))$ weak estimates.

It is easy to use Chebyshev’s inequality to find a weak estimate of $ N = O( \sigma^2 / \delta \varepsilon^2 )$ .

However, I do not how to find inequality about their median. The wikipedia of median (https://en.wikipedia.org/wiki/Median#The_sample_median) says sample median asymptotically normal but this does not give a bound for specific $ N$ . Any suggestion is welcome.