Prerequisite:

The probabilistic method proves the existence of a combinatorial object - a graph colouring, a good code, an expander - without constructing it explicitly. The argument is startlingly simple: show that a random construction produces the desired object with positive probability. If $P(\text{object has property}) > 0$, then at least one object with that property must exist.

The method is due primarily to Paul Erdős, who used it throughout the 1940s–60s to establish bounds that deterministic methods could not match.

The Core Principle

Principle. If $X$ is a random variable with $\mathbb{E}[X] > 0$, then $P(X > 0) > 0$, so there exists an outcome with $X > 0$.

Similarly: if $\mathbb{E}[X] < k$ for an integer-valued non-negative random variable $X$, then $P(X = 0) > 0$, so there exists an outcome where $X = 0$.

This averaging argument is the probabilistic method in its purest form.

Ramsey Numbers: The Foundational Example

Definition. The Ramsey number $R(k, k)$ is the smallest $n$ such that any 2-colouring of the edges of $K_n$ contains a monochromatic $k$-clique.

Theorem (Erdős, 1947). $R(k, k) > 2^{k/2}$.

Proof. Let $n = 2^{k/2}$. Colour each edge of $K_n$ red or blue independently, each with probability $1/2$. For a fixed set $S$ of $k$ vertices, let $A_S$ be the event that $S$ forms a monochromatic clique. There are $\binom{k}{2}$ edges within $S$, and they are all the same colour with probability $2 \cdot (1/2)^{\binom{k}{2}} = 2^{1-\binom{k}{2}}$.

The expected number of monochromatic $k$-cliques is:

$$\mathbb{E}[\text{# mono } k\text{-cliques}] = \binom{n}{k} \cdot 2^{1-\binom{k}{2}}$$

Using $\binom{n}{k} \leq n^k/k!$ and $\binom{k}{2} = k(k-1)/2$:

$$\binom{n}{k} \cdot 2^{1-\binom{k}{2}} \leq \frac{n^k}{k!} \cdot 2^{1-k(k-1)/2}$$

Substituting $n = 2^{k/2}$:

$$= \frac{2^{k^2/2}}{k!} \cdot 2^{1-k(k-1)/2} = \frac{2}{k!} \cdot 2^{k^2/2 - k(k-1)/2} = \frac{2}{k!} \cdot 2^{k/2}$$

For large $k$ this is less than 1 (since $k! \gg 2^{k/2+1}$). Therefore the expected number of monochromatic cliques is less than 1, so with positive probability there are no monochromatic $k$-cliques. Thus a 2-colouring of $K_n$ with no monochromatic $k$-clique exists, proving $R(k,k) > n = 2^{k/2}$. $\square$

The best known upper bound is $R(k,k) \leq 4^k$. Closing this exponential gap is one of the major open problems in combinatorics.

The Lovász Local Lemma

The basic probabilistic method fails when every outcome violates some constraint - we cannot conclude the bad events are avoidable just because each one individually has small probability if they are many and correlated. The Lovász Local Lemma (LLL) handles exactly this situation.

Theorem (Lovász Local Lemma, symmetric version). Let $A_1, \ldots, A_n$ be events in a probability space. If:

  1. $P(A_i) \leq p$ for all $i$, and
  2. Each $A_i$ is mutually independent of all but at most $d$ of the other events,

and if $ep(d+1) \leq 1$ (where $e = 2.718\ldots$), then:

$$P!\left(\bigcap_{i=1}^n \overline{A_i}\right) > 0$$

That is, with positive probability none of the bad events occur.

Proof sketch (Erdős-Spencer). By induction, one shows $P(A_i \mid \bigcap_{j \in S} \overline{A_j}) \leq p$ for any $S$ not containing $i$. The key is that the independence structure limits how the conditioning on far-away events can inflate $P(A_i)$. The condition $ep(d+1) \leq 1$ is tight up to the constant $e$.

The general (asymmetric) version replaces the uniform bound $p$ with individual $p_i$ and requires finding $x_i \in [0,1)$ with $p_i \leq x_i \prod_{j \in \Gamma(i)}(1-x_j)$, where $\Gamma(i)$ is the neighbourhood of $A_i$ in the dependency graph.

Application: $k$-SAT

Consider a $k$-CNF formula with $m$ clauses, each clause involving exactly $k$ variables. Each clause is violated (bad event $A_i$) by exactly $2^{-k}$ of assignments. Each clause shares variables with at most $k(m_{\max}-1)$ others where $m_{\max}$ is the number of clauses per variable. If each variable appears in at most $r$ clauses, the dependency degree is $d \leq k \cdot r$. The LLL condition $e \cdot 2^{-k} \cdot (kr + 1) \leq 1$ is satisfied when $r \leq 2^k/(ek) - 1/k$, guaranteeing a satisfying assignment exists.

The Alteration Method

Sometimes the random construction almost works but has a few defects. The alteration method constructs randomly and then removes or repairs the defects.

Example (independent set). Let $G = (V, E)$ be a graph with $n$ vertices and $m$ edges. Include each vertex in a random set $S$ independently with probability $p$. Then $\mathbb{E}[|S|] = pn$. For each edge $(u,v) \in E$ with both endpoints in $S$, remove one endpoint. The resulting set $S'$ is independent, and:

$$\mathbb{E}[|S'|] \geq pn - \mathbb{E}[\text{# edges in } S] = pn - p^2 m$$

Setting $p = n/(2m)$ (assuming $m \geq n/2$) gives $\mathbb{E}[|S'|] \geq n^2/(4m)$. This recovers the Turán bound: every graph with $m$ edges has an independent set of size at least $n^2/(2n + 2m) \approx n/(2 + 2m/n)$.

The Second Moment Method

The basic method shows $P(X > 0) > 0$ when $\mathbb{E}[X] > 0$. But if $X$ is highly concentrated, $P(X > 0) \approx 1$. The second moment method quantifies this.

Theorem (Paley-Zygmund inequality). For a non-negative random variable $X$ with $\mathbb{E}[X] > 0$:

$$P(X > 0) \geq \frac{(\mathbb{E}[X])^2}{\mathbb{E}[X^2]}$$

Proof. By Cauchy-Schwarz:

$$\mathbb{E}[X] = \mathbb{E}[X \cdot \mathbf{1}_{X > 0}] \leq \sqrt{\mathbb{E}[X^2]} \cdot \sqrt{P(X > 0)}$$

Squaring and rearranging gives the result. $\square$

The ratio $(\mathbb{E}[X])^2 / \mathbb{E}[X^2]$ is small when $X$ has high variance relative to its mean, and close to 1 when $X$ is concentrated. When $\mathbb{E}[X^2] = \Theta((\mathbb{E}[X])^2)$, we conclude $P(X > 0) = \Omega(1)$, which (combined with $\mathbb{E}[X] = \Omega(1)$) shows that $X$ is positive with constant probability.

Examples

Expanders from random graphs. A $d$-regular graph $G$ on $n$ vertices is an expander if every set $S$ with $|S| \leq n/2$ satisfies $|N(S)| \geq (1+\alpha)|S|$ for some expansion constant $\alpha > 0$. Random $d$-regular graphs are expanders with high probability for any fixed $d \geq 3$. The probabilistic argument shows the expected number of “bad” sets (violating the expansion) is $o(1)$, so with high probability no bad set exists. Constructing explicit expanders with the same parameters requires deep algebraic tools (Ramanujan graphs via the theory of modular forms); the probabilistic proof establishes existence far more simply.

LLL and satisfiability. The algorithmic LLL (Moser-Tardos, 2010) not only proves existence but efficiently finds the good object: whenever $ep(d+1) \leq 1$, repeatedly choose a violated constraint uniformly at random and resample the variables in that constraint. The algorithm terminates in expected polynomial time. This is a rare case where a purely existential probabilistic argument was later converted into an efficient algorithm, resolving a longstanding open question about the constructivity of the probabilistic method.

The probabilistic method illustrates a broader principle in mathematics: to prove that something exists, it can suffice to show that a random process produces it with positive probability. The method’s power lies in choosing the right probability space.

Read Next: