The Probabilistic Method — Mathematics Knowledge System

Overview

The probabilistic method, pioneered largely by Paul Erdős starting in the 1940s, proves that a combinatorial structure with a desired property exists by showing that a randomly constructed structure has that property with positive probability — without ever exhibiting the structure explicitly. If the probability of failure (of NOT having the desired property) is strictly less than 1, then some outcome must succeed, so an object with the property must exist. The simplest and most common version is the first-moment method: compute the expected number of 'bad events' in a random construction, and if that expectation is less than 1, some outcome has zero bad events. The technique turned Ramsey theory, graph coloring, and coding theory upside down by proving existence results that no known explicit construction could match.

Intuition

If the average value of a nonnegative integer random variable is less than 1, it cannot be that every single outcome takes a value of 1 or more — some outcome must hit 0, because an average of, say, 0.47 is only achievable if a good chunk of outcomes are actually 0. This is exactly the pigeonhole principle in disguise, applied to averages instead of counts. The classic use is Erdős's 1947 lower bound on Ramsey numbers: color the edges of K_n red/blue uniformly at random, and let X count the monochromatic k-cliques. Compute E[X] by summing, over every k-subset of vertices, the probability that subset is monochromatic. If that sum is less than 1, then some actual coloring of K_n has zero monochromatic k-cliques — proving R(k,k) must exceed n, all without ever describing what that winning coloring looks like.

Formal Definition

Definition

Let X be a random variable counting some undesired feature (e.g. monochromatic cliques) in a randomly generated structure. The first-moment principle states:

\mathbb{E}[X] < 1 \implies \Pr[X = 0] > 0

First-moment (expectation) principle

\Pr[X=0] > 0 \implies \exists \text{ an outcome with } X=0

Existence conclusion

\binom{n}{k}\, 2^{\,1-\binom{k}{2}} < 1 \implies R(k,k) > n

Classic lower bound for Ramsey numbers (Erdős, 1947)

Derivation

Derive Erdős's lower bound on the Ramsey number R(k,k) using the first-moment method on a uniformly random 2-coloring of K_n's edges.

\text{Color each edge of } K_n \text{ red or blue independently with probability } 1/2 \text{ each.}

The random construction.

\text{For a fixed k-subset } S \text{ of vertices, } \Pr[S \text{ is monochromatic}] = 2 \cdot \left(\tfrac12\right)^{\binom{k}{2}}

S has C(k,2) edges; all must be the same color, and there are 2 color choices (all-red or all-blue).

X = \sum_{S : |S|=k} \mathbf{1}[S \text{ monochromatic}]

X counts the total number of monochromatic k-cliques over all C(n,k) possible k-subsets.

\mathbb{E}[X] = \binom{n}{k}\cdot 2^{1-\binom{k}{2}}

Linearity of expectation: sum the per-subset probability over all C(n,k) subsets.

\text{If } \binom{n}{k}2^{1-\binom{k}{2}} < 1, \text{ then some coloring has } X=0, \text{ so } R(k,k) > n.

Apply the first-moment principle: expectation below 1 forces some outcome to be exactly 0.

Proofs

Erdős's probabilistic lower bound R(4,4) > 6

$\text{Randomly 2-color the edges of } K_6, \text{ each edge red/blue independently with probability } 1/2.$ (Set up the random construction on n=6 vertices, aiming to show a monochromatic K_4 is avoidable.)
$\Pr[\text{a fixed 4-subset is monochromatic}] = 2\cdot(1/2)^{\binom{4}{2}} = 2\cdot(1/2)^6 = 2/64 = 1/32$ (A 4-subset has C(4,2)=6 edges; all 6 must match in color, with 2 possible matching colors.)
$\mathbb{E}[X] = \binom{6}{4}\cdot \frac{1}{32} = 15 \cdot \frac{1}{32} = \frac{15}{32} \approx 0.469$ (Linearity of expectation over the C(6,4)=15 possible 4-subsets of the 6 vertices.)
$\mathbb{E}[X] = 15/32 < 1 \implies \Pr[X=0] > 0$ (The first-moment principle: since the average is below 1, some coloring must achieve X=0 monochromatic 4-cliques.)
$R(4,4) > 6$ (A coloring of K_6 with zero monochromatic K_4's exists, so 6 is not enough vertices to force one — hence R(4,4) must exceed 6.)

Properties

First-moment principle

\mathbb{E}[X] < 1 \implies \Pr[X=0] > 0

Linearity of expectation (key computational tool)

\mathbb{E}\left[\sum_i X_i\right] = \sum_i \mathbb{E}[X_i], \text{ even if the } X_i \text{ are dependent}

Erdős-type Ramsey bound

\binom{n}{k}2^{1-\binom{k}{2}} < 1 \implies R(k,k) > n

Applications

Randomized algorithm analysis (e.g. random SAT-solvers, hashing schemes) uses first-moment arguments to prove that good configurations exist and are not too rare.

Worked Examples

A triangle has C(3,2)=3 edges; all 3 must match color, and there are 2 matching colors.
$\Pr[\text{fixed triangle monochromatic}] = 2\cdot(1/2)^3 = 2/8 = 1/4$
There are C(5,3)=10 triangles among 5 vertices; apply linearity of expectation.
$\mathbb{E}[X] = 10 \cdot \tfrac14 = 2.5$

Answer: The expected number of monochromatic triangles is 2.5 — this is above 1, so the first-moment method alone can't show R(3,3)>5 this way (in fact R(3,3)=6, so K_5 does have colorings with zero monochromatic triangles, just not guaranteed by this bound).

Practice Problems

Difficulty 5/10

What is the probability that a fixed set of 3 edges in a random 2-coloring are all the same color?

Difficulty 6/10

Compute E[X], the expected number of monochromatic K_3's in a random 2-coloring of K_6.

Difficulty 8/10

Using the bound C(n,k)·2^(1-C(k,2)) < 1, verify it holds for n=6,k=4 (giving R(4,4)>6) and explain why it fails at n=8.

Common Mistakes

Common Mistake

Thinking the probabilistic method constructs the desired object explicitly.

It only proves existence — it shows the probability of failure is less than 1, hence a success outcome exists — but gives no explicit recipe for finding that outcome.

Common Mistake

Believing E[X] < 1 means X is usually close to 1.

E[X] < 1 only guarantees SOME outcome has X=0 (assuming X is a nonnegative integer random variable); it says nothing about how likely X=0 is, which could be a very small positive probability.

Quiz

The first-moment method concludes that a structure with a desired property exists whenever:

the expected number of 'bad' occurrences is less than 1the variance of X is zeroX is always exactly 0the probability of success is exactly 1/2

Erdős's 1947 probabilistic argument for lower-bounding Ramsey numbers works by:

explicitly building a graph coloring with no monochromatic cliqueshowing the expected number of monochromatic k-cliques in a random coloring is below 1, so some coloring must avoid them entirelycomputing R(k,k) exactly via a formulausing the pigeonhole principle on graph degrees

Summary

The probabilistic method proves existence by showing a randomly built structure has the desired property with positive probability, without explicit construction.
The first-moment principle: if E[X] < 1 for a nonnegative-integer-valued 'bad event count' X, some outcome has X=0.
Erdős's classic 1947 application lower-bounds Ramsey numbers: a random 2-coloring of K_n has expected monochromatic-clique count below 1 for suitable n, proving R(k,k) > n.
Concretely, C(n,k)·2^(1-C(k,2)) < 1 implies R(k,k) > n; e.g. at n=6, k=4 this gives 15/32 < 1, so R(4,4) > 6.
The method underlies existence proofs across graph theory, coding theory, and randomized algorithms.

References

BookAlon, N. and Spencer, J.H. The Probabilistic Method, 4th ed. Wiley.
WebsiteWikipedia — Probabilistic method