= Solution
For each column $X_j$, the normalized score is
$$
W_j=\frac1nX_j^T\varepsilon=\frac1n\sum_{i=1}^nX_{ij}\varepsilon_i.
$$
The errors are independent <Rademacher random variables>, and $\lVert X_j\rVert_2^2=n$. The <Hoeffding lemma> therefore makes $W_j$ a <sub-Gaussian random variable> with variance proxy $1/n$, so
$$
\mathbb P(|W_j|>t)\leq2e^{-nt^2/2}.
$$
The <union bound> with $t=\lambda/2$ gives
$$
\mathbb P(\Omega)
\geq1-2p\exp\!\left(-\frac{n\lambda^2}{8}\right).
$$
For $\lambda=A\sqrt{\log p/n}$ this becomes
$$
\mathbb P(\Omega)\geq1-2p^{,1-A^2/8}.
$$
In particular, if $A>\sqrt8$, the lower bound tends to one as $p\to\infty$.
Back to article page
