Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 223 (Robust Statistics)

Let $m=F^{-1}(1/2)$ be the unique median. The influence function of the sample median isaway from $m$. Its second moment, equivalently the asymptotic distribution of a sample median, givesNo symmetry assumption is used: the density is evaluated at the actual median of $F$.

Write $F=(1-ϵ)\Phi +ϵH$ and assume $0<ϵ<1/2$. If $m$ is its median, thenMoreover its density satisfies $f(m)\ge (1-ϵ)\varphi (m)$. Since the standard normal density decreases with $|m|$, the smallest possible density at the median occurs at either endpoint. PutThe two endpoints are $\pm q_{ϵ}$ by normal symmetry. The bound is attained by choosing a contaminating density supported strictly to the right of $q_{ϵ}$, or symmetrically to the left of $-q_{ϵ}$, with zero density at the selected median. Therefore

Every symmetric contaminated distribution has median zero, soA symmetric contaminating density supported away from zero attains equality. HenceThis is strictly smaller than the unrestricted answer because $q_{ϵ}>0$ and $\varphi (q_{ϵ})<\varphi (0)$. Asymmetric contamination can move the median into a region of lower nominal density.

The normal location score is $x-\theta$. Under a bound on gross-error sensitivity, the variance-minimizing influence curve clips this score. For $b>0$, define the Huber scoreThe optimal B-robust estimator is the Huber location estimator ${\hat{\theta }}_b$ defined byEquivalently, it has the explicit optimization formwhere the Huber loss isAt $N(\theta ,1)$ its normalized influence function is

The gross-error bound corresponding to $b$ isIt is strictly increasing becauseso the numerator of $c^{\prime }(b)$ is positive. FurthermoreThus $b\in (0,\infty )$ corresponds exactly to $c\in (\sqrt{\pi /2},\infty )$.

As $b\downarrow 0$, the Huber estimating equation approaches the sign equationwhose solution is the sample median. Hence the most B-robust location M-estimator is the median, with minimum gross-error sensitivity

Let $\Delta ={\theta }_1-{\theta }_0>0$. For one observation from the unit-variance normal location family,The sample log-likelihood ratio is therefore $n{T}_n$. By the Neyman-Pearson lemma, the level-$\alpha$ most powerful test rejects for a sufficiently large likelihood ratio, equivalently when $T_n>C_{\alpha }$, with $C_{\alpha }$ chosen to give null rejection probability $\alpha$.

The functional isThe influence function of an expectation functional isBecause $\psi$ is affine with nonzero slope, this is unbounded under both $F_{{\theta }_0}$ and $F_{{\theta }_1}$.

Now letThenSince $a\le {\psi }_{a,b}(x)\le b$, this influence function is bounded for both hypotheses. Clipping the log-likelihood contribution prevents one extreme observation from having unbounded effect on the statistic.

Put $r(x)=f_{{\theta }_1}(x)/f_{{\theta }_0}(x)$. The proposed first density can be writtenIts integral is continuous and strictly decreasing in $c$, tends to infinity as $c\downarrow 0$, and tends to $1-ϵ$ as $c\to \infty$. Hence a unique $c>0$ makes its integral one. Since $g_{0,c}\ge (1-ϵ)f_{{\theta }_0}$,for the density $h_0=[g_{0,c}-(1-ϵ)f_{{\theta }_0}]/ϵ$.

Similarly,Its integral is continuous and strictly increasing from $1-ϵ$ to infinity as $d$ ranges from zero to infinity. The unique normalizing $d>0$ givesfor a density $h_1$. Thus $G_0\in {\mathcal{P}}_{ϵ}(F_{{\theta }_0})$ and $G_1\in {\mathcal{P}}_{ϵ}(F_{{\theta }_1})$.

Assume $d<c$. Directly comparing the two piecewise densities givesSincewe obtainThus the sample log-likelihood ratio is $n{S}_n$ with truncation values $a=\log d$ and $b=\log c$. Rejecting for large $S_n$ is exactly the likelihood-ratio test between the two least-favorable contaminated distributions.

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.

Replace the same last $k$ vectors by $(100,\dots ,100)$. Applying part a to each independent Gaussian coordinate shows that the probability its contaminated coordinate median exceeds $ϵ$ is at least $1-e^{-c_{ϵ}n}$. Independence across coordinates and Bernoulli's inequality giveFor $n$ sufficiently large as a function of $d$ and $ϵ$, the last expression is at least $1/2$. On this event,which proves the stated lower bound for the supremum over adversarial perturbations.

The coordinatewise median suffers a contamination error of order $ϵ\sqrt{d}$ with constant probability. In contrast, the Tukey median under an isotropic Gaussian model satisfies a high-probability Euclidean error bound of orderwith probability at least $1-\delta$, up to universal constants. Its contamination term is dimension-free. Thus coordinatewise estimation loses a factor $\sqrt{d}$ in its dependence on adversarial contamination.