The Lovász local lemma allows a slight relaxation of the independence condition: 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.
This lemma is most commonly used in the probabilistic method, in particular to give existence proofs.
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.
In 2020, Robin Moser and Gábor Tardos received the Gödel Prize for their algorithmic version of the Lovász Local Lemma, which uses entropy compression to provide an efficient randomized algorithm for finding an outcome in which none of the events occurs.
Lemma I (Lovász and Erdős 1973; published 1975) If
then there is a nonzero probability that none of the events occurs.Lemma II (Lovász 1977; published by Joel Spencer[3]) If
where e = 2.718... is the base of natural logarithms, then there is a nonzero probability that none of the events occurs.Lemma II today is usually referred to as "Lovász local lemma".
then there is a nonzero probability that none of the events occurs.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).
be a finite set of events in the probability space Ω.
is not adjacent to events which are mutually independent).
is positive, in particular The symmetric version follows immediately from the asymmetric version by setting to get the sufficient condition since As is often the case with probabilistic arguments, this theorem is nonconstructive and gives no method of determining an explicit element of the probability space in which no event occurs.
However, algorithmic versions of the local lemma with stronger preconditions are also known (Beck 1991; Czumaj and Scheideler 2000).
More recently, a constructive version of the local lemma was given by Robin Moser and Gábor Tardos requiring no stronger preconditions.
By using the principle of mathematical induction we prove that for all
The induction here is applied on the size (cardinality) of the set
We need to show that the inequality holds for any subset of
We have from Bayes' theorem We bound the numerator and denominator of the above expression separately.
Expanding the denominator by using Bayes' theorem and then using the inductive assumption, we get The inductive assumption can be applied here since each event is conditioned on lesser number of other events, i.e. on a subset of cardinality less than
To get the desired probability, we write it in terms of conditional probabilities applying Bayes' theorem repeatedly.
To see this, imagine picking a point of each color randomly, with all points equally likely (i.e., having probability 1/11) to be chosen.
The 11n different events we want to avoid correspond to the 11n pairs of adjacent points on the circle.
Whether a given pair (a, b) of points is chosen depends only on what happens in the colors of a and b, and not at all on whether any other collection of points in the other n − 2 colors are chosen.
This implies the event "a and b are both chosen" is dependent only on those pairs of adjacent points which share a color either with a or with b.
There are 11 points on the circle sharing a color with a (including a itself), each of which is involved with 2 pairs.
This means there are 21 pairs other than (a, b) which include the same color as a, and the same holds true for b.
The worst that can happen is that these two sets are disjoint, so we can take d = 42 in the lemma.
This gives By the local lemma, there is a positive probability that none of the bad events occur, meaning that our set contains no pair of adjacent points.
This implies that a set satisfying our conditions must exist.