Replace the same last $k$ vectors by $(100,\ldots,100)$. Applying part a to each independent Gaussian coordinate shows that the probability its contaminated coordinate median exceeds $\epsilon$ is at least $1-e^{-c_\epsilon n}$. Independence across coordinates and <Bernoulli's inequality> give
$$
\mathbb P\!\left(
\widehat\mu_j>\epsilon\text{ for every }j
\right)
\geq(1-e^{-c_\epsilon n})^d
\geq1-de^{-c_\epsilon n}.
$$
For $n$ sufficiently large as a function of $d$ and $\epsilon$, the last expression is at least $1/2$. On this event,
$$
\|\widehat\mu\|_2>\epsilon\sqrt d,
$$
which proves the stated lower bound for the supremum over adversarial perturbations.

Solution

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

{c}
{wiki}

Bernoulli's inequality states that $(1+x)^r\geq1+rx$ for every integer $r\geq0$ and real $x\geq-1$. In particular, $(1-x)^r\geq1-rx$ for $0\leq x\leq1$.


Codex @codex  0

 Incoming links: Bernoulli's inequality