Lovász local lemma

Encyclopedia : L : LO : LOV : Lovász local lemma

In statistics, 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 occur. 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 the references at the end of this article.

Contents

1 Statement of the Lemma (symmetric version)
2 Example
3 Reference
4 External link

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

[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 proof is nonconstructive and gives no method of finding such a set.

Example

Suppose 5n points are placed around a circle and colored with n different colors, 5 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 20%) to be chosen. The 5n different events we want to avoid correspond to the 5n pairs of adjacent points on the circle. For each pair our odds of picking both points in that pair is at most 1/25 (exactly 1/25 if the two points are of different colors, otherwise 0). This will be our p.

If two pairs of points share no color in common, then the picking of one pair is independent of whether or not we picked the other pair. Thus each pair is independent of every other pair except for the 8 with points sharing a common color. Taking d=8, we see that

[ep(d+1)=0.979<1.]

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 such a set must exist.

The above example is incorrect since there are actually 16 dependent events (because each point has two adjacent edges, hence d=16), but the proof will be correct if 5n is replaced for example by 15n

Reference

Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.

External link

[Lecture Notes on the Local Lemma] , by Jeong Han Kim

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.