Lovász local lemma

In probability theory, if a large number of events are all independent of one another, then there is a positive (possibly small) probability that none of the events will occur. The Lovász local lemma (proved in 1975 by László Lovász and Paul Erdős) 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 Alon and Spencer (2000).

tatement of the Lemma (symmetric version)

Let "A₁, A₂,..., A_k" 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.

If

:$e\; p\; (d+1)\; le\; 1$

(where e =2.718...), then there is a nonzero probability that none of the events occur.

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).

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 1 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. 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 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.

References

*cite book
author = Alon, Noga; Spencer, Joel H.
year = 2000
title = The probabilistic method
edition = 2nd ed.
location = New York
publisher = Wiley-Interscience
id = ISBN 0-471-37046-0

*cite journal
author = Beck, J.
title = An algorithmic approach to the Lovász local lemma, I
journal = Random Structures and Algorithms
volume = 2
issue = 4
pages = 343–365
year = 1991

*cite journal
title = Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma
author = Czumaj, Artur; Scheideler, Christian
journal = Random Structures & Algorithms
year = 2000
volume = 17
issue = 3–4
pages = 213–237
doi = 10.1002/1098-2418(200010/12)17:3/4<213::AID-RSA3>3.0.CO;2-Y

*cite conference
author = Erdős, Paul; Lovász, László
title = Problems and results on 3-chromatic hypergraphs and some related questions
editor = A. Hajnal, R. Rado, and V. T. Sós, eds.
booktitle = Infinite and Finite Sets (to Paul Erdős on his 60th birthday)
volume = II
pages = 609–627
publisher = North-Holland
date = 1975
url = http://www.cs.elte.hu/~lovasz/scans/LocalLem.pdf

External links

* [http://research.microsoft.com/research/theory/jehkim/Lectures/ProbCombi/Chap5_5.pdf Lecture Notes on the Local Lemma] , by Jeong Han Kim