Median-of-means estimator

A median-of-means estimator divides a sample into $k$ disjoint groups, computes the sample mean in each group, and returns a sample median of those group means. A single extreme observation changes only one group mean, so it need not dominate the final answer.

Here is a finite-variance guarantee. Let the observations be independent and identically distributed random variables with mean $\mu$ and variance $v>0$. Take odd $k$, groups of equal size $m=\lfloor n/k\rfloor$, and discard any unused observations. By Chebyshev inequality, each group mean differs from $\mu$ by more than $2\sqrt{v/m}$ with probability at most $1/4$.

The groups are independent. If their sample median exceeds this error, at least half of the groups must be bad. Applying Hoeffding inequality to their bad-group indicators givesThus an odd $k\ge 8\log (1/\delta )$ gives confidence at least $1-\delta$, provided there are enough observations. If $n\ge 2k$, then $m\ge n/(2k)$, giving error at most $2\sqrt{2vk/n}$. This is a sub-Gaussian deviation bound under finite variance; it does not assert that the observations are sub-Gaussian random variables. The block argument above derives the bound from the two stated inequalities. Choosing too many groups makes the individual means noisy.