Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 205 / 3 / c / Solution

For each column $X_j$, the normalized score isThe errors are independent Rademacher random variables, and $\Vert X_j{\Vert }_2^2=n$. The Hoeffding lemma therefore makes $W_j$ a sub-Gaussian random variable with variance proxy $1/n$, soThe union bound with $t=\lambda /2$ givesFor $\lambda =A\sqrt{\log p/n}$ this becomesIn particular, if $A>\sqrt{8}$, the lower bound tends to one as $p\to \infty$.