Median-of-Mean

Suppose that we have an algorithm $A$ that estimates the mean $E[Y]$ of a random variable $Y$ within some specified range $r$ with probability $\rho > \frac{1}{2}$ . We can derive a new algorithm $A^*$ from $A$ that boosts the successful probability to $1 - \delta$ , as follows:

Repeat $A$ for $m = \frac{1}{2 (\rho - 0.5)^2 } \ln \frac{1}{\delta}$ times.

Take the median of the $m$ outputs.

To prove it, define the indicator random variable

X_i = \begin{cases} 1, \text{ if the } i \text{-th output of } A \text{ is within the range } r \\ 0, \text{otherwise} \end{cases}

for $1 \le i \le m$ . Then $E[X_i] = \rho > 0.5$ . Let $\mu = E \left[\sum_{i = 1}^m X_i \right] = m\rho$ .

By Hoeffding's inequality, for $\lambda > 0$ ,

\Pr \left[ \left| \sum_{i = 1}^m X_i - \mu \right| \ge \lambda \right] \le \exp \left(- \frac{2\lambda^2}{m} \right)

Replacing $\lambda$ with $\mu - 0.5m$ , and $m$ with $m = \frac{1}{2 (\rho - 0.5)^2 }\ln \frac{1}{\delta}$ , we get

\begin{aligned} \Pr \left[ \sum_{i = 1}^m X_i \le 0.5m \right] &\le \Pr \left[ \left| \sum_{i = 1}^m X_i - \mu \right| \ge m(\rho - 0.5) \right] \\ &\le \exp \left(- 2m(\rho - 0.5)^2 \right) \\ &= \delta \end{aligned}

Note that if more than half of $A$ outputs are correct, then the output of $A^*$ is correct. This happens with probability at least $1 - \delta$ .