= Maximum of finitely many Rademacher linear forms
{title2=$\Pr(\max_i|u_i^T\xi|\le\alpha)>1-2me^{-\alpha^2/2}$}
For independent <Rademacher random variables> and $\|u_i\|_2\le1$, this bound holds for $\alpha>0$. The moment-generating function satisfies $\prod_j\cosh(tu_{ij})\le e^{t^2/2}$, with strict inequality for a nonzero vector and $t>0$. Applying the exponential Markov bound to both tails and then the <union bound> proves a strict failure bound; a zero vector has failure probability zero. At $\alpha=\sqrt{2\log(2m)}$, the success probability is strictly positive, ensuring a sign vector with all linear forms below that threshold.
Back to article page
