Robust estimation of the mean

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.

Asymptotic estimation of $A_n$

Let $ A_n$ represent the number of integers that can be written as the product of two element of $ [[1,n]]$ .

I am looking for an asymptotic estimation of $ A_n$ .

First, I think it’s a good start to look at the exponent $ \alpha$ such that :

$ $ A_n = o(n^\alpha)$ $

I think we have : $ 2 < alpha $ . To prove this lower bound we use the fact that the number of primer numbers $ \leq n$ is about $ \frac{n}{\log n}$ . Hence we have the trivial lower bound (assuming $ n$ is big enough) :

$ $ \frac{n}{\log n} \cdot \binom{ E(\frac{n}{\log n})}{2} = o(n^3)$ $

Now is it possible to get a good asymptotic for $ A_n$ and not just this lower bound ? Is what I’ve done so far correct ?

Thank you !