Second moments and Paley–Zygmund

Consider a variable equal to $n^2$ with probability $1/n$ and zero otherwise. Its expectation is n, yet its probability of being positive tends to zero. The second moment is $n^3$, so the square of the mean is small relative to the second moment. This ratio detects the rare, excessively large outcomes that invalidate an existence-with-high-probability inference. A useful second-moment argument must therefore compare scales, not merely show that both moments are finite.

For a sum of indicators, expand its square before estimating. The diagonal terms are the indicators themselves, because squaring a zero-one variable changes nothing. Distinct pairs contribute joint occurrence probabilities, with ordered pairs counted twice relative to unordered pairs. If two configurations use disjoint sets of underlying independent random choices, their joint probability factors. Sharing vertices does not always mean sharing random choices: triangles in an independent-edge graph are independent when they share only a vertex.

For a nonnegative square-integrable variable with positive mean, write its expectation using only the event where it is positive. Cauchy–Schwarz bounds that expectation by the square root of the second moment times the probability of positivity. Rearranging gives a lower bound, not an upper bound, on existence. Equality of the first two relevant moment scales is favorable. If the variance divided by the squared mean tends to zero, this existence lower bound tends to one.

Paley–Zygmund retains the same idea above a nonzero threshold. For a parameter theta between zero and one, the contribution from values at most theta times the mean is at most that threshold. The remaining contribution must carry at least the fraction one minus theta of the mean, and Cauchy–Schwarz controls it. We use the event strictly greater than the threshold. When the variable is integer valued, translate that event carefully; a threshold equal to one corresponds to at least two, not at least one.

An alternative presentation applies Chebyshev to the deviation equal to the mean. Since X=0 is such a deviation, a small relative variance forces positivity with high probability. More generally it forces X divided by its mean to approach one in probability. This is stronger than merely having a nonvanishing chance of finding an object. For a sequence of combinatorial counts, both the diagonal contribution and every class of correlated pairs must be negligible at the squared-mean scale.

The method can fail even when the desired conclusion is true. Counting a very clustered family of witnesses may produce a huge second moment; changing the witness count, conditioning on coarse information, or using a weighted count can improve matters. Failure of a particular moment bound is not a counterexample to existence. In the binomial calculation below, independence makes the variance easy, allowing the direction and thresholds of the inequalities to be inspected without a long overlap classification.