= Solution
Choose a fixed $\alpha<1/2$. On the stated high-probability event, strictly more than half of the block means satisfy, simultaneously for every $\|v\|_2\leq1$,
$$
\left|\overline X_{B_j}^Tv-\mu_0^Tv\right|
\leq c_\alpha
\sqrt{\frac{\max\{\operatorname{tr}(\Sigma),\|\Sigma\|_2k\}}n}.
$$
The <median> of a collection with a strict majority in an interval lies in that interval. Hence the same bound holds for $|\operatorname{MOM}_k(Xv)-\mu_0^Tv|$ uniformly in $v$. Part b then gives
$$
\|\widehat\mu(X)-\mu_0\|_2
\leq2c_\alpha
\sqrt{\frac{\max\{\operatorname{tr}(\Sigma),\|\Sigma\|_2k\}}n}
$$
with probability at least $1-e^{-k/c_\alpha}$. Renaming the constant proves the claim.
Back to article page
