the Paley-Zygmund inequality
/ PAY-lee ZIG-mund /
The Paley-Zygmund inequality is a one-line companion to the second moment method that gives a quantitative lower bound on the probability that a non-negative random variable is a fixed fraction of its mean. Where Chebyshev controls how often X is far from its mean from above and below, Paley-Zygmund controls the lower tail directly: it guarantees that X is reasonably large with probability bounded away from zero, again using only the first two moments. It is the precise statement behind the slogan 'a non-negative variable with small relative variance is positive with constant probability'.
The inequality states that for a non-negative random variable X with finite second moment and any theta in [0,1], P(X > theta E[X]) >= (1 - theta)^2 (E[X])^2 / E[X^2]. Setting theta = 0 it recovers P(X > 0) >= (E[X])^2 / E[X^2], the cleanest second-moment positivity bound. The proof is a single application of Cauchy-Schwarz: write E[X] = E[X; X <= theta E[X]] + E[X; X > theta E[X]], bound the first piece by theta E[X], and apply Cauchy-Schwarz to the second piece to get E[X; X > theta E[X]] <= sqrt(E[X^2]) sqrt(P(X > theta E[X])). Rearranging gives the stated bound. The ratio (E[X])^2 / E[X^2] is the key quantity — it is close to 1 exactly when the variance is small relative to the mean squared.
Its value is that it converts the second-moment condition Var(X) = o(E[X]^2) into a genuine lower bound on a probability, not just a statement that P(X = 0) is small, and it does so with an explicit constant for any threshold theta. In random graph theory it is the standard way to show a count is at least a constant fraction of its mean with constant probability, which combined with a concentration result (a martingale or Janson bound) often upgrades to with high probability. The honest caveat is that Paley-Zygmund gives only a constant lower bound on the probability when the moment ratio is bounded; to get probability tending to 1 you still need the variance to be of strictly smaller order, exactly as in the second moment method.
If X counts something with E[X^2] <= (1 + o(1))(E[X])^2 (the second-moment condition), then P(X > 0) >= (E[X])^2/E[X^2] -> 1, so X is positive with high probability. If instead E[X^2] = 2(E[X])^2, Paley-Zygmund at theta=0 only guarantees P(X > 0) >= 1/2 — a constant, not whp; you would then add a concentration step to finish.
P(X > theta E[X]) >= (1-theta)^2 (E[X])^2 / E[X^2]: a lower bound on the lower tail from two moments.
Paley-Zygmund alone gives only a constant probability lower bound when the moment ratio is bounded; probability tending to 1 still requires Var(X) = o(E[X]^2), the full second-moment condition.