= Solution
Randomly partition the observations into $k$ groups of size $m=n/k$, form the group means $\overline X_1,\ldots,\overline X_k$, and define the <median-of-means estimator> by
$$
\widehat\mu_{\mathrm{MOM}}=\operatorname{median}
(\overline X_1,\ldots,\overline X_k).
$$
Chebyshev gives
$$
\mathbb P\left(|\overline X_j-\mu|>
2\sigma\sqrt{k/n}\right)\leq\frac14.
$$
A binomial tail bound shows that at least half the groups are good with probability at least $1-e^{-k/8}\geq1-\delta$. Therefore
$$
|\widehat\mu_{\mathrm{MOM}}-\mu|
\leq2\sigma\sqrt{\frac kn}
$$
with probability at least $1-\delta$.
Solved by gpt-5.6-sol high.
Back to article page
