Lovász Local Lemma

When bad events are sparsely dependent, some outcome avoids them all: ep(d+1) ≤ 1 forces P( A_i) > 0.

The idea

Theorem (Lovász Local Lemma (symmetric form)).

Let $A_{1}, \dots, A_{n}$ be events with $\mathbb{P}(A_{i}) \le p$ for every $i$, each of them mutually independent of all but at most $d$ of the others. If $e\,p\,(d+1) \le 1$, then $\mathbb{P}\!\left(\bigcap_{i} \overline{A_{i}}\right) > 0.$

The conclusion says that some outcome avoids every event at once. In applications the $A_{i}$ are the ways a random construction can fail.

Compare the union bound, which estimates the probability that at least one $A_{i}$ occurs by $np$ and so proves an escape exists only when $np < 1$. That condition worsens as the events multiply: with a million events of probability one in a thousand each, the union bound proves nothing.

The local lemma replaces the global count with a local one. The number $n$ does not appear in its hypothesis at all; in its place stands $d$, the dependency degree, the largest number of other events any single $A_{i}$ depends on. The events may be arbitrarily numerous, provided each depends on only a few of the others.

The conclusion is existence and nothing more: the probability of avoiding every event is positive, often extremely small. But positive probability means at least one outcome succeeds, which is all an existence proof requires.

Ways to work on it

• Walkthrough. The symmetric statement of the local lemma and the probability threshold it sets.
• Practice. Check whether the local lemma's condition holds for given parameters.
• Hardest. Apply the local lemma to a satisfiability problem.

Not sure where to start? Take the ten-question placement test.