## 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 !