= Spectral norm bound for a centered Bernoulli adjacency matrix
{title2=$\mathbb E\|A-\mathbb EA\|_{\mathrm{op}}\leq C\sqrt n$}
For independent <Bernoulli distribution> upper-triangular entries of a symmetric zero-diagonal <adjacency matrix of a graph>, put $W=A-\mathbb EA$. For a unit vector $x$, $x^\top Wx=2\sum_{i<j}x_ix_jW_{ij}$ has sub-Gaussian variance proxy at most $\sum_{i<j}x_i^2x_j^2\leq1/2$, by the <Hoeffding lemma>. Hence $\mathbb P(|x^\top Wx|>u)\leq2e^{-u^2}$. The <volumetric bound for Euclidean metric nets> gives a $1/4$-<metric net> of the <unit sphere> with at most $9^n$ points. The <quadratic form net bound> gives $\|W\|_{\mathrm{op}}\leq2\max_x|x^\top Wx|$ on that net. The <union bound> gives $\mathbb P(\|W\|_{\mathrm{op}}>2\sqrt{n\log9+\log2+s})\leq e^{-s}$; integrating this tail proves the displayed expectation bound.
Back to article page
