the first moment method

Here is a deceptively powerful question: how do you prove that some elaborate object — a graph with no large clique, a colouring with no monochromatic line, a solution to a puzzle — does NOT exist, or conversely that one almost certainly DOES, without ever constructing it? The first moment method does this by counting on average. It connects a count's expectation to whether the count can be zero.

The idea rests on a one-line observation about a non-negative integer count N (say, the number of 'bad' configurations): if the average count is small, the count is usually zero. Formally, by Markov's inequality, P(N >= 1) <= E[N]. So if E[N] < 1, then P(N >= 1) < 1, which means P(N = 0) > 0 — there must exist an outcome with no bad configurations at all. To compute E[N], you write N as a sum of indicator variables, one per potential bad configuration, and use linearity of expectation: E[N] = sum of P(each configuration is bad). Linearity is the magic — it needs no independence whatsoever.

This is a cornerstone of the probabilistic method in combinatorics. To prove something exists, show a random construction produces it with positive probability (E[bad count] < 1, so a bad-free outcome exists). To prove an event is rare, show its expected count tends to 0, forcing the probability to 0. The honest limit: a small expectation guarantees the count is OFTEN zero but cannot guarantee it is ALWAYS positive — for the reverse direction (showing N >= 1 with high probability) a large E[N] is not enough, because the count could be huge sometimes and zero usually. That gap is exactly what the second moment method fixes.