Paley–Zygmund inequality

Remarks

Proof: split $E[Z] = E[Z \mathbf{1}_{\set{Z \le \theta E[Z]}}] + E[Z \mathbf{1}_{\set{Z > \theta E[Z]}}]$. The first term is at most $\theta E[Z]$, and by the Cauchy–Schwarz inequality the second is at most $\sqrt{E[Z^2] \, P(Z > \theta E[Z])}$. Rearranging gives the bound. With $\theta = 0$ it becomes the second moment method: $P(Z > 0) \ge E[Z]^2 / E[Z^2]$. Example: if $Z$ counts the triangles in an Erdős–Rényi random graph and $E[Z^2] / E[Z]^2 \to 1$, then $P(Z > 0) \to 1$, so a triangle exists with high probability. The bound is a lower bound on the probability of being large, while Markov's inequality and Chebyshev's inequality give upper bounds. The hypothesis $Z \ge 0$ is needed: the constant $Z = -1$ has $E[Z]^2 / E[Z^2] = 1$, but with $\theta = 0$ the event $\set{Z > 0}$ is empty.

Going deeper

For a student

The inequality is the basis of the second moment method in combinatorics and random graphs, where one shows that a count $Z$ is positive with high probability. In analysis, Paley and Zygmund used it for random series, to show that a random trigonometric series is large with positive probability. It complements the first moment method, which uses $P(Z > 0) \le E[Z]$ for integer-valued $Z \ge 0$.