Motivation
The union bound proves that some outcome avoids every bad event when the sum of their probabilities is less than one. It can fail when there are many bad events, even if each event is rare and interacts with only a few others. The Lovász local lemma exploits this sparse dependency structure to prove that an outcome avoiding all bad events still exists.
The conclusion is existential. The proof below does not provide an efficient algorithm for finding the outcome. It also requires a precise dependency condition: being pairwise independent of each distant event separately is not enough to justify conditioning on all of them together.
Definitions
Definition 6.5.1
(Dependency graph)
Let be events in a probability space. A dependency graph is an undirected graph on the event indices such that each is independent of the joint sigma-algebra generated by all events with and not adjacent to . Write for the neighbors of . This joint independence means that is independent of every event determined by the collection of nonneighbors, including an intersection of their complements.
For independent random variables, events depending on disjoint sets of variables are independent. A valid dependency graph can be obtained by joining events whose variable sets overlap, even if some joined events happen to be independent. Extra edges are allowed but can weaken the bound.
Theorems
Theorem 6.5.2
(General local lemma)
Suppose there are numbers such that, for every ,
Then .
Theorem 6.5.3
(Symmetric local lemma)
If each event has probability at most , the dependency graph has maximum degree at most , and , then the probability of avoiding every bad event is positive.
Proof: conditional bad-event probabilities
Proof
(Conditional bad-event probabilities by induction)
We first prove by induction on that, for every index and every set not containing ,
and the conditioning event has positive probability. The empty-set case follows from the hypothesis because the product is at most one. Positivity for a set of avoided events follows by ordering those events and applying the already established conditional bounds: each successive avoidance has conditional probability at least .
For the induction step, split into and . Let be the event that all events indexed by are avoided, and the event that all events indexed by are avoided. The event has positive probability by the induction hypothesis. Joint independence of from its nonneighbors gives .
Order the indices of . By the induction hypothesis, conditioned on and on avoiding earlier events of , each next bad event has probability at most its . The relevant conditioning sets omit that next index and have size smaller than . Therefore
Now
The last inequality uses the hypothesis and the fact that is a subset of . This completes the induction. Finally, order all bad events and multiply their successive conditional avoidance probabilities. Each is at least , proving the general lemma.
Proof X-ray
Where each hypothesis is used
Three hypotheses are used, each at one step. Joint independence of from its nonneighbors is used once, to replace by , where is the intersection of the complements of all events in . Pairwise independence from each of them would not suffice, as the counterexample below shows. The induction hypothesis is applied to the neighbors in with conditioning sets strictly smaller than ; this is why the induction runs on , and why nothing has to be assumed about how the neighbors depend on one another. The numerical hypothesis is used at the end to absorb the denominator: dividing by loses at most the factors of neighbors outside , each of which lies in .
Proof: the symmetric criterion
Proof
(From the general lemma to the symmetric criterion)
For , choose for every . Since each degree is at most ,
The final inequality follows from . Thus implies the hypothesis of the general lemma. For , the bad events are jointly independent in the required sense, and each has probability at most ; their avoidance probability is the product of positive factors. The case of no events is vacuous.
Worked examples
Worked example 6.5.4
(A sparse 3-CNF formula)
Take a 3-CNF formula in which each clause has three distinct variables and shares variables with at most one other clause. Under independent fair random assignments, a clause is false with probability . Joining clauses that share a variable gives maximum dependency degree . Since , some assignment satisfies every clause.
Worked example 6.5.5
(The union bound may be too weak)
For ten such clauses, the sum of their individual failure probabilities is , so the union bound alone gives no positive lower bound on the probability that all are satisfied. If the dependency condition in the previous example holds, the local lemma nevertheless guarantees a satisfying assignment.
Worked example 6.5.6
(Independent events)
Suppose 100 bad events are mutually independent and each has probability . Their probability sum is 25, but the probability of avoiding all of them is . The dependency graph has degree zero, illustrating why the number of events alone is not the relevant obstruction.
Worked example 6.5.7
(Checking a failed criterion)
If and , then . The symmetric criterion does not apply. This calculation does not prove that avoiding all events is impossible; it only says this sufficient test gives no conclusion.
Common mistakes
Counterexample mode
Pairwise independence is not joint independence
Let be independent fair bits and set . The three bits are pairwise independent, but is determined by the pair . Thus the event is independent of each event and separately, yet it is not independent of their intersection. A dependency graph that omits both edges solely because of pairwise independence would not satisfy the definition above.
Common mistake
(Reading a dependency edge as actual dependence)
A dependency edge records that dependence is permitted, not that dependence must actually occur. Adding unnecessary edges remains valid but increases the degree and may make the symmetric inequality fail. Conversely, omitting an edge requires the full joint-independence property, not just a correlation calculation.
Common mistake
(Expecting high probability or an algorithm from existence)
The lemma guarantees positive probability and hence existence. It does not say a uniformly sampled assignment succeeds with high probability, and it does not by itself bound the time needed to find a successful outcome. Constructive versions need additional algorithms and hypotheses.
Applying the lemma carefully
Start by specifying the probability space and the bad events. Then compute or bound each event probability. Construct a graph that satisfies the joint-independence condition and bound its maximum degree; for events defined by independent variables, disjoint variable sets give a convenient justification. Finally check the numerical inequality and translate avoidance of every bad event back into the desired object.
A clause that repeats a variable may have a different failure probability from . A tautological clause is never false. The example assumes three distinct variables so the three required falsifying assignments are independent fair-bit constraints. It counts dependency degree by other clauses sharing at least one variable, not by the number of variables in a clause.
The asymmetric theorem can be useful when some events are much rarer or have fewer neighbors than others. Its parameters are chosen individually, so it may succeed even if a single worst-case pair makes the symmetric criterion fail. Choosing those parameters and checking the products remain part of the proof for each application.
A hypergraph coloring application
Let a finite hypergraph have edges of exactly distinct vertices, and suppose each edge intersects at most other edges. Color every vertex independently red or blue with probability one half each. For an edge , let be the event that all its vertices have the same color. There are two monochromatic color patterns out of , so .
Join two bad events when their hyperedges intersect. An event depends only on the colors of its own edge's vertices and is independent of the joint collection of events on disjoint edges. The dependency graph has maximum degree at most . Hence, whenever
the local lemma gives a coloring with no monochromatic edge. This is a proper two-coloring in the sense that every hyperedge contains both colors. The graph may have many edges; the condition controls local overlap instead of the total number of bad events.
For example, if and every hyperedge meets at most one other, then and . A valid two-coloring exists. The conclusion does not say how to find it efficiently or how many such colorings exist.
An asymmetric calculation
Suppose there are two bad events joined by a dependency edge, with probabilities at most and . Set and . The product conditions are and . The general lemma yields avoidance probability at least .
For just two events, the union bound happens to give the stronger lower bound . The example is intended to show how to verify unequal parameters, not to claim that the local lemma always improves every other bound. In larger sparse systems its advantage can appear when the sum of event probabilities exceeds one.
Keeping the induction well founded
The proof's conditional probabilities require nonzero denominators. At an induction stage for a set , positivity of avoidance for every smaller set follows by multiplying the previously established lower bounds for successive complements. In the split , the conditioning event is positive, and the product bound on conditioned on is positive as well. Hence has positive probability before we divide by it.
The joint-independence assumption is used only on , which is determined by events outside 's neighborhood. The events in may be arbitrarily dependent on and on one another; the induction controls their conditional avoidance probability without assuming independence. Separating these roles avoids the mistaken shortcut of multiplying unconditional avoidance probabilities for neighboring events.
The conditional-probability inequality in the induction is deliberately one-sided. Inside the probability space conditioned on , the event is a subset of , so its probability is at most . Dividing by the positive probability of gives the displayed upper bound. It would be incorrect to replace that inequality by equality unless an additional relationship between and were known.
The product in the general hypothesis ranges over the entire neighborhood, whereas the induction divides only by the factors belonging to . Every factor lies between zero and one, so deleting factors makes the product larger. Consequently the ratio is at most . This is the point where the local numerical hypothesis absorbs the possible loss caused by conditioning on neighboring events.
A positive lower bound can be extremely small. For instance, the product of many factors below one can tend to zero as the number of events grows, even though it is positive for every fixed finite instance. The theorem applies to the finite collection in the statement; infinite versions require separate hypotheses and arguments.
For events defined by independent variables, a simple resampling procedure finds it quickly in expectation.
A natural next question
Can the outcome be found efficiently?
For events defined by independent variables, a simple resampling procedure finds it quickly in expectation.
For events determined by independent random variables, a resampling procedure works: while some bad event holds, resample the variables of one such event. It is known to terminate after a polynomial expected number of resamplings under conditions of the same kind as the lemma's. This proof is a different, algorithmic argument and is not given here.
Summary
The local lemma bounds conditional bad-event probabilities despite sparse dependencies. Joint independence from nonneighbors and the product condition ensure that avoiding each successive event retains positive probability. The symmetric inequality gives a convenient sufficient test, but does not supply a search algorithm.
Exercises
Quick check
(Evaluate for and , and decide whether the symmetric test applies.)
Solution · Answer
The value is , so the test guarantees positive probability of avoiding all events, provided the stated dependency-degree and event-probability bounds hold.
Quick check
(Why can two clauses with disjoint variable sets be nonadjacent in the dependency graph under independent random assignments?)
Solution · Answer
Each falsity event depends only on its clause's variables. Independent assignments to disjoint variable sets give independence from the joint collection of all events based on the other disjoint variable sets.
Quick check
(What does the local lemma conclude if its inequality holds: existence, high probability, or an efficient algorithm?)
Solution · Answer
It concludes that the avoidance event has positive probability, hence at least one avoiding outcome exists. It does not by itself promise high probability or an efficient search.
Quick check
(Give a numerical lower bound for avoiding two independent bad events of probabilities and .)
Solution · Answer
Independence gives exactly . The local lemma supplies a positive lower bound as well, but exact independence gives this sharper value.