Lovász local lemma
Encyclopedia
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 (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) 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. For other versions, see .
then there is a nonzero probability that none of the events occurs.
In 1977 Joel Spencer
published an improvement to this result which he attributed to Lovász: there is a nonzero probability that none of the events occurs already if
(where e
= 2.718... is the base of natural logarithms). This version today is usually referred to as Lovász Local Lemma.
Then Shearer showed that this again can be slightly strengthened by weakening the hypothesis to
(except if 
then to 
); this is the optimal threshold and it implies that the bound
is also sufficient.
The symmetric version follows immediately from the asymmetric version by setting
for all 
to get the sufficient condition
since
.
was given by Robin Moser and Gábor Tardos
requiring no stronger preconditions.
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. For each pair our odds of picking both points in that pair is at most 1/121 (exactly 1/121 if the two points are of different colors, otherwise 0). This will be our p.
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.
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, if a large number of events are all independent
Statistical independence
In probability theory, to say that two events are independent intuitively means that the occurrence of one event makes it neither more nor less probable that the other occurs...
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 (a weaker version was proved in 1975 by László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
and Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
in the article Problems and results on 3-chromatic hypergraphs and some related questions) 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
Probabilistic method
The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the...
, 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. For other versions, see .
Statements of the Lemma (symmetric version)
Let A1, A2,..., Ak be a series 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. Lovász and Erdős showed 1973 (published 1975) that ifthen there is a nonzero probability that none of the events occurs.
In 1977 Joel Spencer
Joel Spencer
Joel Spencer is an American mathematician. He is a combinatorialist who has worked on probabilistic methods in combinatorics and on Ramsey theory. He received his doctorate from Harvard University in 1970, under the supervision of Andrew Gleason...
published an improvement to this result which he attributed to Lovász: there is a nonzero probability that none of the events occurs already if
(where e
E (mathematical constant)
The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...
= 2.718... is the base of natural logarithms). This version today is usually referred to as Lovász Local Lemma.
Then Shearer showed that this again can be slightly strengthened by weakening the hypothesis to
(except if then to ); this is the optimal threshold and it implies that the boundis also sufficient.
Asymmetric Lovász local lemma
A statement of the asymmetric version (which allows for events with different probability bounds) is as follows:- Let
be a finite set of events in the probability space 
. For 
let 
denote a subset of 
such that 
is independent from the collection of events 
. If there exists an assignment of reals 
to the events such that
- then the probability of avoiding all events in
is positive, in particular
The symmetric version follows immediately from the asymmetric version by setting
for all to get the sufficient conditionsince
.Constructive versus non-constructive
Note that, 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 lemmaAlgorithmic Lovász local lemma
In theoretical computer science, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence....
was given by Robin Moser and Gábor Tardos
Gábor Tardos
Gábor Tardos is a Hungarian mathematician, currently a professor and Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science...
requiring no stronger preconditions.
Example
Suppose 11n points are placed around a circle and colored with n different colors, 11 points colored with each color. Then there must be a set of n points containing one point of each color but not containing any pair of adjacent points.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. For each pair our odds of picking both points in that pair is at most 1/121 (exactly 1/121 if the two points are of different colors, otherwise 0). This will be our p.
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.