Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 210 / 1

Let $f(x)=\Vert x{\Vert }_{\infty }$. Away from ties and zero coordinates, its gradient is $\nabla f(x)=\pm e_i$ for a maximizing coordinate $i$. Conditional on $X$, the random variable $⟨\nabla f(X),Y⟩$ is centered Gaussian with variance at most one. The supplied Gaussian concentration inequality therefore givesA Chernoff bound, optimized at $\lambda =4u/{\pi }^2$, yieldsIt remains to bound the mean. For $t>0$, Jensen's inequality and the Gaussian moment-generating function giveTaking $t=\sqrt{2\log (2d)}$ gives $\mathbb{E}\Vert X{\Vert }_{\infty }\le \sqrt{2\log (2d)}$. Consequently