Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 223 / 4 / a / Solution

Assume first that $0<ϵ<1/2$, set $k=\lfloor ϵn\rfloor$, and replace the last $k$ observations by $100$. Among the remaining $m=n-k$ observations, letThe contaminated median exceeds $ϵ$ wheneverThe right-hand threshold divided by $m$ tends toTherefore, for all sufficiently large $n$, it is at most $p_{ϵ}-{\delta }_{ϵ}$ for some ${\delta }_{ϵ}>0$. The Hoeffding inequality givesThe supremum over adversarial perturbations is at least this explicit construction, proving the claim. When $ϵ\ge 1/2$, replacing at least half the sample makes the conclusion immediate.