Lovász local lemma

In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma allows one to relax the independence condition slightly: As long as the events are "mostly" independent from one another and aren't individually too likely, then there will still be a positive probability that none of them occurs. It is most commonly used in the probabilistic method, in particular to give existence proofs.

There are several different versions of the lemma. The simplest and most frequently used is the symmetric version given below. A weaker version was proved in 1975 by László Lovász and Paul Erdős in the article Problems and results on 3-chromatic hypergraphs and some related questions. For other versions, see (Alon & Spencer 2000).

Let A₁, A₂,..., A_k be a sequence of events such that each event occurs with probability at most p and such that each event is independent of all the other events except for at most d of them.

Lemma I (Lovász and Erdős 1973; published 1975) If

Lemma II (Lovász 1977; published by Joel Spencer) If

Lemma II today is usually referred to as "Lovász local lemma".

Lemma III (Shearer 1985) If

The threshold in lemma III is optimal and it implies that the bound

is also sufficient.

A statement of the asymmetric version (which allows for events with different probability bounds) is as follows:

Lemma (asymmetric version). Let ${\displaystyle {\mathcal {A}}=\{A_{1},\ldots ,A_{n}\}}$ be a finite set of events in the probability space Ω. For ${\displaystyle A\in {\mathcal {A}}}$ let ${\displaystyle \Gamma (A)}$ denote the neighbours of ${\displaystyle {\mathcal {A}}}$ in the dependency graph (In the dependency graph, event A is not adjacent to events which are mutually independent). If there exists an assignment of reals ${\displaystyle x:{\mathcal {A}}\to [0,1)}$ to the events such that

...
Wikipedia