Median-of-means estimator: Definition & Examples

The median-of-means estimator estimates a population mean by averaging observations within disjoint blocks, then taking the median of those block averages. It can protect an expected-payoff estimate against the influence of a few extreme observations without changing the target to the median payoff.

Two operations, two jobs

For clarity, use an odd number $k$ of equally sized blocks, each containing $m$ observations, so $n=km$ . With block index sets $B_1,\ldots,B_k$ , calculate

Z_j=\frac{1}{m}\sum_{i\in B_j}X_i, \qquad \widehat{\mu}_{\mathrm{MoM}}=\operatorname{median}(Z_1,\ldots,Z_k).

Averaging within blocks reduces sampling noise. Taking the median across blocks limits how much a minority of extreme block averages can move the result. An odd $k$ gives a unique middle-ranked value. With even $k$ , a median convention must be specified; this article uses odd $k$ throughout.

The target is

\mu=\mathbb{E}[X]

. It is not the population median, and the finite-sample estimator need not be unbiased. Increasing the number of blocks also shortens each block when

n

is fixed: more votes come with noisier individual averages. The confidence level therefore informs the block count. These distinctions are central to the finite-variance analysis.

A large value reaches one block

Take nine hypothetical payoff observations in arbitrary units, assigned to these fixed illustrative blocks:

Block	Observations	Block mean
1	$0,1,2$	$1$
2	$1,2,3$	$2$
3	$1,2,100$	$103/3\approx34.3333$

The median of $1,2,103/3$ is $2$ . The ordinary sample mean, using all nine observations, is

\bar{x}=\frac{112}{9}\approx12.4444, \qquad \widehat{\mu}_{\mathrm{MoM}}=2.

Fixed blocks contain 0, 1, 2; 1, 2, 3; and 1, 2, 100 arbitrary units. Their means are 1, 2 and 34.3333. Median of means is 2, while the pooled mean is 12.4444.

Original hypothetical arithmetic: the large observation affects one block mean. The figure does not specify a population mean or establish which estimate is closer to it.

The raw-data median also happens to be

2

here. That coincidence does not make the two procedures equivalent. Median-of-means sorts block averages, whereas the raw-data median sorts individual observations.

Nor does the value

100

prove that an observation is corrupted. A genuine rare payoff belongs to the population whose expectation is being estimated. This table demonstrates the aggregation mechanism, not a rule for deleting outliers.

Why a majority can sharpen confidence

Assume

X_1,\ldots,X_n

are independent and identically distributed, with mean

\mu

and finite, positive variance

\sigma^2

. Choose the disjoint index blocks before examining their values. Equal block size gives

\text{Var}(Z_j)=\sigma^2/m

Here is the explicit constant calculation behind Lugosi and Mendelson's Theorem 2. Put

r=2\sigma/\sqrt{m}

. Chebyshev's inequality gives

\mathbb{P}(\lvert Z_j-\mu\rvert>r) \leq\frac{\sigma^2/m}{r^2}=\frac14.

Let $I_j$ indicate that this block is outside the interval $\mu-r,\mu+r]$ . The indicators are independent, lie in $[0,1]$ , and have $\mathbb{E}[\sum_j I_j]\leq k/4$ . If the median is outside the interval, at least $(k+1)/2$ blocks are outside. Relaxing that threshold to $k/2$ , [Hoeffding's inequality yields

\begin{aligned} \mathbb{P}(\lvert\widehat{\mu}_{\mathrm{MoM}}-\mu\rvert>r) &\leq \mathbb{P}\left(\sum_{j=1}^k I_j-\mathbb{E}\left[\sum_{j=1}^k I_j\right]\geq\frac{k}{4}\right)\\ &\leq\exp\left(-\frac{2(k/4)^2}{k}\right)=e^{-k/8}. \end{aligned}

For desired failure probability $0<\delta<1$ , choose an odd integer $k\geq8\log(1/\delta)$ , with $k\leq n$ and $k$ dividing $n$ . Then, with probability at least $1-\delta$ ,

\lvert\widehat{\mu}_{\mathrm{MoM}}-\mu\rvert \leq2\sigma\sqrt{\frac{k}{n}}.

The logarithm is natural. If no suitable divisor exists, a precise alternative is to choose an admissible odd $k$ , use $m=\lfloor n/k\rfloor$ observations per block and discard the remaining observations by a rule fixed in advance. Keep the bound as $2\sigma/\sqrt{m}$ , with failure probability at most $e^{-k/8}$ ; $n$ is then the original sample size and $km$ the size actually used. For very small $\delta$ , the required $k$ may exceed $n$ , making this construction unavailable. Computing the point estimate needs no known $\sigma$ ; turning this theoretical radius into a numerical interval needs a justified variance bound or additional scale analysis.

What the guarantee leaves open

This result accommodates heavy tails with finite variance. It does not supply the same radius when variance is infinite. It also assumes an uncontaminated iid sampling model: resistance to corruption is a separate question.

For the three-block example, one block mean can move arbitrarily while the median remains between the other two. Two corrupted observations placed in different blocks can instead move a majority of the block means arbitrarily far. The number of affected blocks matters, not just the fraction of corrupted points. Even uncorrupted blocks must be close to the target for their majority to be useful.

The fixed example is not a random-sampling guarantee. Under the iid assumptions above, a fixed partition of indices is valid; selecting groups after inspecting values needs a separate argument. For serial financial returns, disjoint blocks need not be independent. Shuffling dependent observations does not establish independence. A time-series application needs a dependence-aware construction and a bound justified under its dependence assumptions.

For the expectation and variance calculations used here, see Expectation, Variance and Covariance (public preview; full lesson with a free signed-in account).

Sources

Devroye, L., Lerasle, M., Lugosi, G. and Oliveira, R. I. (2016), Sub-Gaussian mean estimators, §§2.3.2 and 4.1: construction and confidence-dependent mean estimation.
Lugosi, G. and Mendelson, S. (2019), Mean estimation and regression under heavy-tailed distributions—a survey, §2.1, Theorem 2 and proof: the finite-variance block bound and its majority argument.

Two operations, two jobs

A large value reaches one block

Why a majority can sharpen confidence

What the guarantee leaves open

Sources

Related terms

Expected value

Median

Outlier

Variance