Consider i.i.d. random variables $\delta_{ij}\sim\text{Ber}(p)$, where $i,j\in[n]$. Assuming that $pn\geq \log(n)$, show that $$\mathbb{E}\max_{i\in[n]}\sum_{j=1}^n(\delta_{ij}-p)^2 \leq Cpn.$$
This is Exercise 6.6.2 from High-Dimensional Probability Book by Roman Vershynin.
And here is my try: Since $\sum_{j=1}^n(\delta_{ij}-p)^2$ are subgaussian (they are bounded),
$$\mathbb{E}\max_{i\in[n]}\sum_{j=1}^n(\delta_{ij}-p)^2 \lesssim \max_{i\in[n]}\|\sum_{j=1}^n(\delta_{ij}-p)^2\|_{\psi_2}\log^{1/2}(n).$$
Now it boils down to estimating $\|\sum_{j=1}^n(\delta_{ij}-p)^2\|_{\psi_2}$ for each fixed $i$. Simple calculation shows
$$\sum_{j=1}^n(\delta_{ij}-p)^2 = np^2 + (1-2p)\sum_{j=1}^n \delta_{ij}.$$
And I would like to have the bound for $\|\sum_{j=1}^n(\delta_{ij}-p)^2\|_{\psi_2}$ to be of order $\sqrt{np}$. However, if I use the inequality
$$\|\sum_{j=1}^n(\delta_{ij}-p)^2\|_{\psi_2}^2 \lesssim \sum_{j=1}^n\|(\delta_{ij}-p)^2\|_{\psi_2}^2,$$
then the bound is only of $O(\sqrt{n})$. So my question is, are the inequalities I use too loose?
Best Answer
I would say the main issue with your approach is that the tail behavior of the sum of your bounded random variables is not described precisely using only subgaussianity. Note that $$\mathsf E(\delta_{ij}-p)^2 = p(1-p)\le p\,.$$ and $$\mathsf E (\delta_{ij}-p)^4\le 2p\,.$$
So by Bernstein inequality,
$$\begin{align*}\Pr\left(\sum_{j=1}^n (\delta_{ij}-p)^2\ge np+t\right)&\le \Pr\left(\sum_{j=1}^n (\delta_{ij}-p)^2\ge np(1-p)+t\right)\\ &\le \exp\left(-\frac{t^2/2}{2np+t/3}\right)\\ &\le \exp\left(-\frac{Ct^2}{np}\right)+\exp(-Ct)\,.\end{align*}$$
This implies the following tail inequality for the maximum after a union bound:
$$\Pr\left(\max_{i\in [n]}\sum_{j=1}^n (\delta_{ij}-p)^2\ge np+t\right)\le n \exp\left(-\frac{Ct^2}{np}\right)+n\exp(-Ct)\,.$$
Now we integrate to get an upper bound on the expectation:
$$\begin{align*}\mathsf{E}\left(\max_{i\in [n]}\sum_{j=1}^n (\delta_{ij}-p)^2\right) &=\int_0^\infty \Pr\left(\max_{i\in [n]}\sum_{j=1}^n (\delta_{ij}-p)^2\ge u\right) \, \text{d}u\\ &\le np+\int_{np}^\infty \Pr\left(\max_{i\in [n]}\sum_{j=1}^n (\delta_{ij}-p)^2\ge u\right) \, \text{d}u\\ &\le np+\int_0^\infty \min\left(1,ne^{-Ct^2/np}\right)\,\text{d}t+\int_0^\infty \min\left(1,ne^{-Ct}\right)\,\text{d}t\\ &\le np+C\sqrt{np\log n}+C\log n\\ &\le C np\,.\end{align*}$$
As a side note, under the same assumption $p\ge \log n/n$, we also have $\mathsf{E} \lVert \delta\rVert_2\le Cnp$. It implies your result, although it is slightly harder to prove.