Problem: (Page 19 in "Vershynin, Roman (2018). High-Dimensional Probability. Cambridge University Press. ISBN 9781108415194.")
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.
As you mentioned, using Chebyshev's inequality, we can easily prove that $N = O(\frac{\sigma^2}{\epsilon^2}) $ samples are enough for an $\epsilon$-accurate estimate of the mean with probability $\frac{3}{4}$.
Now asume that we have $k$ estimates $(\hat{\mu}_1, \hat{\mu}_2, ..., \hat{\mu}_k)$ that each of the are $\epsilon$-accurate. Each of them need $N = O(\frac{\sigma^2}{\epsilon^2}) $ samples. Let $X_i = 1(|\hat{\mu}_i - \mu|>\epsilon)$, i.e. the indicator of wrong answers. $X_i$s are iid Bernoulli random variables with p = $\frac{1}{4}$.
Let $\hat{\mu} = \mathrm{med}(\hat{\mu}_1, \hat{\mu}_2, ..., \hat{\mu}_k)$:
\begin{equation} P(|\hat\mu - \mu|>\epsilon) = P(\sum_{i = 1}^{k}X_i>\frac{k}{2}) = P(\sum_{i = 1}^{k}(X_i-\frac{1}{4})>\frac{k}{4}) \end{equation}
Using the general Hoeffding inequality for bounded random variables, Theorem 2.2.6 of Vershynin, Roman (2018). High-Dimensional Probability, we can write
$$P(\sum_{i = 1}^{k}(X_i-\frac{1}{4})>\frac{k}{4})<\exp(-\frac{k}{8})$$ thus $$P(|\hat\mu - \mu|>\epsilon) < \exp(-k/8) = \delta \rightarrow k = O(log(\delta^{-1}))$$
So by having $O\big(log(\delta^{-1})\frac{\sigma^2}{\epsilon^2}\big)$ samples, we can have an $\epsilon$-accurate estimate with probability $1-\delta$.