Bounding rows of random matrices 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?
 A: 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)^4\le 2p$, so by Bernstein inequality
$$\mathsf{P}\left(\sum_{j=1}^n (\delta_{ij}-p)^2\ge t\right)\le \exp\left(-\frac{t^2/2}{2np+t/3}\right)\le \exp\left(-\frac{Ct^2}{np}\right)+\exp(-Ct).$$
This implies the following tail inequality for the maximum after a union bound:
$$\mathsf{P}\left(\max_{i\in [n]}\sum_{j=1}^n (\delta_{ij}-p)^2\ge 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 \mathsf{P}\left(\max_{i\in [n]}\sum_{j=1}^n (\delta_{ij}-p)^2\ge t\right) \, dt\\
&\le \int_0^\infty \min\left(1,ne^{-Ct^2/np}\right)\,dt+\int_0^\infty \min\left(1,ne^{-Ct}\right)\,dt\\
&\le 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.
