高级算法 (Fall 2016)/Nonconstructive Proof of Lovász Local Lemma

From EtoneWiki
Jump to: navigation, search

Given a sequence of events , we use the dependency graph to describe the dependencies between these events.

Definition (dependency graph)
Let be a sequence of events. A graph on the set of vertices is called a dependency graph for the events if for each , , the event is mutually independent of all the events .

The notion of mutual independence between an event and a set of events is formally defined as follows.

Definition (mutual independence)
An event is said to be mutually independent of events , if for any disjoint , it holds that
.
Example
Let be a set of mutually independent random variables. Each event is a predicate defined on a number of variables among . Let be the unique smallest set of variables which determine . The dependency graph is defined by
iff .

The following lemma, known as the Lovász local lemma, first proved by Erdős and Lovász in 1975, is an extremely powerful tool, as it supplies a way for dealing with rare events.

Lovász Local Lemma (symmetric case)
Let be a set of events, and assume that there is a such that the followings are satisfied:
  1. for all , ;
  2. the maximum degree of the dependency graph for the events is , and
.
Then
.

We will prove a general version of the local lemma, where the events are not symmetric. This generalization is due to Spencer.

Lovász Local Lemma (general case)
Let be the dependency graph of events . Suppose there exist real numbers such that and for all ,
.
Then
.

To see that the general LLL implies symmetric LLL, we set for all . Then we have .

Assume the condition in the symmetric LLL:

  1. for all , ;
  2. ;

then it is easy to verify that for all ,

.

Due to the general LLL, we have

.

This proves the symmetric LLL.

Now we prove the general LLL by the original induction proof.

Proof.

First, apply the chain rule. We have

.

Next we prove by induction on that for any set of events ,

.

The local lemma follows immediately by the above chain rule.

For , this is obvious because

.

For general , let be the set of vertices adjacent to in the dependency graph, i.e. event is mutually independent of .

By conditional probability, we have

.

First, we bound the numerator. Due to that is mutually independent of , we have

Next, we bound the denominator. Applying the chain rule, we have

which by the induction hypothesis, is at least

where is the set of edges in the dependency graph.

Altogether, we prove the induction hypothesis

Due to the chain rule, it holds that