The Probabilistic Method: Proving That a Good Object Exists

A surprising number of existence theorems in combinatorics and algorithm design are proved by showing that a random object is good with positive probability. The proof does not exhibit a good object, does not say how to find one, and does not even need to compute the probability. It only needs to show that the probability of failure is strictly less than 1. That is enough to conclude that at least one good object exists, because if none existed the failure probability would be 1.

The technique is worth understanding for two reasons. It settles questions that have no constructive answer in the obvious sense, and the same probability estimates, when made algorithmic, become the analyses of randomized algorithms that do find the objects. The gap between “exists” and “can be found efficiently” is where most of the interesting work sits.

A counting argument that avoids counting

The simplest form of the argument is the one used for Ramsey-type bounds and for the existence of graphs with no short cycles and high chromatic number. Suppose the claim is that some graph on n vertices has a property P. Choose a random graph from a distribution over graphs on n vertices, and show that the probability of P is positive. Since the distribution assigns positive probability to every graph in its support, a positive probability for P means at least one graph has it.

The classic illustration is a hypergraph 2-coloring. Given a hypergraph with m edges, each of size k, color each vertex red or blue independently with probability 1/2. For a single edge, the probability that all its k vertices receive the same color is 2 · 2^{-k} = 2^{1-k}. If m · 2^{1-k} < 1, then by the union bound the probability that some edge is monochromatic is below 1, so a proper 2-coloring exists. The condition is m < 2^{k-1}, a purely counting condition, and the argument gives no way to find the coloring in less than exponential time in the worst case.

The union bound is doing all the work, and its weakness is the price. It ignores all overlap between the bad events, so it needs the number of events times the probability of one to be small. When the edges of the hypergraph share vertices heavily, the events are positively correlated in a way the union bound cannot exploit, and the condition m < 2^{k-1} is far stronger than necessary. The local lemma exists to exploit exactly that structure.

The local lemma and the dependency graph

The Lovász local lemma replaces the global union bound with a condition on a dependency graph. Each bad event A_i is a subset of the random choices; two events are adjacent in the dependency graph if they share a choice. The lemma states that if each A_i has probability at most p, each A_i is adjacent to at most d others, and e · p · (d + 1) ≤ 1 (with e the base of the natural logarithm), then the probability that none of the bad events occurs is strictly positive.

The proof is by induction on the set of events being avoided. The key estimate is that conditioning on the non-occurrence of some events can increase the probability of another event by at most a factor, and the factor accumulates multiplicatively along paths in the dependency graph. The condition e p (d+1) ≤ 1 is exactly what makes the product stay bounded, and the e comes from the inequality (1 - 1/(d+1))^{d+1} < 1/e.

Applying it to the hypergraph coloring: each edge is a bad event with probability 2^{1-k}, and an edge depends on the edges that share at least one vertex with it. If each edge intersects at most D others, the condition becomes e · 2^{1-k} · (D + 1) ≤ 1, which permits D up to roughly 2^{k-1}/e. The gain over the union bound is not in that constant: the union bound needs the total number of edges m below 2^{k-1}, while the local lemma only needs the number of edges touching any one edge to be below 2^{k-1}/e. A hypergraph with exponentially many edges, each overlapping only a small fraction of the others, satisfies the lemma and fails the union bound by an exponential margin.

The catch is that the local lemma in this form is non-constructive. It proves a coloring exists, and the inductive proof does not translate into an algorithm, because the conditional probabilities it computes are not efficiently computable from the input. That gap stood for roughly two decades.

Making the lemma constructive

The algorithmic version, due to Moser and Tardos, works by resampling. Start with a random assignment. While some bad event occurs, pick one such event and resample all the choices it depends on, independently from their original distributions. The claim is that this process terminates, and that the expected number of resamplings is bounded by a function of the local lemma parameters.

The analysis is a witness argument rather than a direct potential function. Each resampling step is charged to a “witness”: a tree of events in the dependency graph rooted at the event being fixed, where each node’s event was made true by the resampling at its parent. The probability that a particular witness tree of size t arises is bounded by p^t times a product of factors that the local lemma condition keeps below a constant, so the expected total number of resamplings is linear in the number of events when the condition holds with slack.

For the hypergraph coloring, this gives an algorithm that starts with a random coloring and repeatedly fixes monochromatic edges by recoloring their vertices. The number of recolorings is linear in the number of edges under the local lemma condition, so the running time is polynomial. The existence proof became an algorithm without changing the probability estimates, only the interpretation of the induction.

import random

def two_color(edges, max_rounds=10**6):
    """edges: list of tuples of vertex ids. Resample monochromatic edges."""
    verts = sorted({v for e in edges for v in e})
    color = {v: random.randrange(2) for v in verts}
    for _ in range(max_rounds):
        bad = [e for e in edges if len({color[v] for v in e}) == 1]
        if not bad:
            return color
        for v in random.choice(bad):
            color[v] = random.randrange(2)
    return None   # the local lemma condition is what rules this out

The loop is the entire algorithm. Its termination is not obvious from the code, and the analysis that establishes it is the content of the constructive version. The max_rounds guard is a concession to implementations that must terminate even when the input violates the condition the analysis assumes.

Derandomization and the method of conditional expectations

An existence proof by the probabilistic method often yields a deterministic algorithm through the method of conditional expectations. The idea is to fix the random choices one at a time, at each step choosing the value that keeps the conditional expectation of the cost at most its unconditional value. Since the unconditional expectation is below the target, and each step does not increase it, the final assignment is at least as good as the average.

For the hypergraph coloring with the union bound condition, the conditional expectation of the number of monochromatic edges can be computed exactly after fixing some vertices: each unfixed edge contributes its probability of becoming monochromatic given the fixed colors, and the sum is the expectation. Choosing the color for the next vertex that minimizes this sum keeps the expectation non-increasing. After all vertices are fixed the count is an integer at most the initial expectation, which is below 1, so it is 0.

The cost is the computation of the conditional expectation at each step. Done naively it is a pass over all edges per vertex, giving O(nm) time, which is polynomial but often worse than the randomized algorithm it replaces. The randomized version terminates in expected linear time under the same conditions, so derandomization here trades a guarantee for a factor in the exponent.

Derandomization matters most when the randomness is unacceptable for reasons other than speed: reproducibility of a compiled artifact, a setting where no entropy source is available, or an adversarial environment in which the random choices could be predicted. In those settings the conditional-expectation method gives the same quality guarantee with no coin flips at all.

What the method cannot do

The probabilistic method proves existence with a distribution fixed in advance. If the distribution is badly chosen, the argument fails even when the object exists, and there is no systematic way to find a better distribution other than insight into the structure. The method is a proof technique, not an algorithm for discovering proofs.

The local lemma’s condition is sufficient, not necessary, and the gap can be large. There are settings where a good object exists and the local lemma cannot prove it, so the constructive version does not apply even though a different algorithm might find the object.

The constructive version’s expected running time is polynomial only under the local lemma condition with slack. At the boundary of the condition the expected number of resamplings grows, and the analysis gives a bound that is polynomial in the number of events but with an exponent that depends on the parameters.

The resampling algorithm also needs to detect a violated event efficiently. For hypergraph coloring that is a scan; for a constraint satisfaction problem with a large domain it may require an index over the constraints, and the cost of maintaining that index can dominate the resampling itself.

These limits are why the probabilistic method sits beside the algorithmic uses of randomness rather than replacing them. The existence results it produces feed into the design of algorithms, and the analyses of those algorithms reuse the same inequalities. The tail bounds that convert an expectation into a guarantee, described in Randomized Recurrences and the Indicator Variable Method, are the same Chernoff and union-bound estimates that appear in the existence proofs. The hashing applications in Universal Hashing and Guarantees That Hold for Every Input are the clearest case where a probabilistic existence argument became a practical data structure: a family of hash functions with a good expected behaviour exists, and choosing one at random from the family makes the guarantee hold for any fixed input.