随机算法 (Fall 2015)/Lovász Local Lemma
Lovász Local Lemma
Suppose that we are give a set of "bad" events . We want to know that it is possible that none of them occurs, that is:
Obviously, a necessary condition for this is that for none of the bad events its occurrence is certain, i.e. for all . We are interested in the sufficient condition for the above. There are two easy cases:
- Case 1: mutual independence.
If all the bad events are mutually independent, then
and hence this probability is positive if for all .
- Case 2: arbitrary dependency.
On the other extreme, if we know nothing about the dependencies between these bad event, the best we can do is to apply the union bound:
which is positive if . This is a very loose bound, however it cannot be further improved if no further information regarding the dependencies between the events is assumed.
Lovász Local Lemma (symmetric case)
In most situations, the dependencies between events are somewhere between these two extremal cases: the events are not independent of each other, but on the other hand the dependencies between them are not total out of control. For these more general cases, we would like to exploit the tradeoff between probabilities of bad events and dependencies between them.
The Lovász local lemma is such a powerful tool for showing the possibility of rare event under limited dependencies. The structure of dependencies between a set of events is described by a dependency graph, which is a graph with events as vertices and each event is adjacent to the events which are dependent with it in the dependency graph.
Definition (dependency graph) - Let be a set of events. A graph with set of vertices is called a dependency graph for the events if every event is mutually independent of all the events in .
The maximum degree of the dependency graph is a very useful information, as it tells us that every event among is dependent with how many other events at most.
- Remark on the mutual independence
- In probability theory, an event is said to be independent of events if for any disjoint , we have
- ,
- that is, occurrences of events among have no influence on the occurrence of .
- 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 as that any two events are adjacent in if and only if they share variables, i.e. .
The following theorem was proved by Erdős and Lovász in 1975 and then later improved by Lovász in 1977. Now it is commonly referred as the Lovász local lemma. It is a very powerful tool, especially when being used with the probabilistic method, 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 the followings hold:
- for every event ;
- every event is mutually independent of all other events except at most of them, and
- .
- Then
- .
Here is the maximum degree of the dependency graph for the events .
Intuitively, the Lovász Local Lemma says that if a rare (but hopefully possible) event is formulated as to avoid a series of bad events simultaneously, then the rare event is indeed possible if:
- none of these bad events is too probable;
- none of these bad events is dependent with too many other bad events;
Here the tradeoff between "too probable" and "too many" is characterized by the condition.
According to a result of Shearer in 1985, the condition of the Lovász Local Lemma cannot be substantially improved if only the bounds on and are known.
Lovász Local Lemma (asymmetric case)
Sometimes when applying the local lemma, a few bad events are much more probable than others or are dependent with more other bad events. In this case, using the same upper bounds on the probability of bad events or on the number of dependent events will be much wasteful. To more accurately deal with such general cases, we need a more refined way to characterize the tradeoff between local dependencies and probabilities of bad events.
We need to introduce a few notations that will be frequently used onwards. Let be a set of events. For every event , we define its neighborhood and inclusive neighborhood as follows:
- inclusive neighborhood: denotes the set of events in , including itself, that are dependent with . More precisely, is mutually independent of all events in .
- neighborhood: , that is, contains the events in that are dependent with , not including itself.
The following is the asymmetric version of the Lovász Local Lemma. This generalization is due to Spencer.
Lovász Local Lemma (general case) - Let be a set of events, where every event is mutually independent of all other events excepts those in its neighborhood in the dependency graph. Suppose there exist real numbers such that for every ,
- .
- Then
- .
- Let be a set of events, where every event is mutually independent of all other events excepts those in its neighborhood in the dependency graph. Suppose there exist real numbers such that for every ,
This generalized version of the local lemma immediately implies the symmetric version of the lemma. Namely, if the followings are satisfied:
- for all ;
- , where is the maximum degree of the dependency graph.
To see this, for every let . Note that .
With the above two conditions satisfied, for all , it is easy to verify:
- ,
which according to the Lovász Local Lemma (general case), implies that
- .
This gives the symmetric version of the local lemma.
A non-constructive proof of LLL
We then give the proof of the generalized Lovász Local Lemma. In particular, this proof is non-constructive, in contrast to the constructive proofs that we are going to introduce later, which are basically algorithms.
Apply the chain rule. The probability that none of the bad events occurs can be expressed as:
It is then sufficient to show that
- ,
which will prove the lemma.
We then prove a slightly more general statement:
- (induction hypothesis) for any distinct events .
The proof is by induction on . For , due to the assumption in the Lovász Local Lemma
- .
For general , assume the hypothesis is true for all smaller . Without loss of generality, assume that are the events among that are dependent with , and is mutually independent of the rest .
Then applying the following basic conditional probability identity
- ,
we have
Due to the mutual independence between and , the becomes
which according to the assumption in the Lovász Local Lemma, is bounded as
Applying the chain rule to the we have
Note that there are always less than events involved, so we can apply the induction hypothesis and have
where the last inequality is due to the fact that .
Combining everything together, we have
As we argued in the beginning, this proves the general Lovász Local Lemma.
Random Search for Exact--SAT
We start by giving the definition of -CNF and -SAT.
Definition (exact--CNF) - A logic expression defined on Boolean variables is said to be a conjunctive normal form (CNF) if can be written as a conjunction(AND) of clauses as , where each clause is a disjunction(OR) of literals, where every literal is either a variable or the negation of a variable.
- We call a CNF formula a exact--CNF if every clause consists of exact distinct literals.
- A logic expression defined on Boolean variables is said to be a conjunctive normal form (CNF) if can be written as a conjunction(AND) of clauses as , where each clause is a disjunction(OR) of literals, where every literal is either a variable or the negation of a variable.
For example:
is an exact--CNF formula.
- Remark
- The notion of exact--CNF is slightly more restrictive than the -CNF, where each clause consists of at most variables. The discussion of the subtle differences between these two definitions can be found here.
A logic expression is said to be satisfiable if there is an assignment of values of true or false to the variables so that is true. For a CNF , this mean that there is a truth assignment that satisfies all clauses in simultaneously.
The exact--satisfiability (exact--SAT) problem is that given as input an exact--CNF formula decide whether is satisfiable.
exact--SAT - Input: an exact--CNF formula .
- Output: whether is satisfiable.
It is well known that -SAT is NP-complete for any . The same also holds for the exact--SAT.
Satisfiability of exact--CNF
Inspired by the Lovasz local lemma, we now consider the dependencies between clauses in a CNF formula.
Given a CNF formula defined over Boolean variables and a clause in , we use to denote the set of variables that appear in . For a clause in a CNF formula , its degree is the number of other clauses in that share variables with . The maximum degree of a CNF formula is .
By the Lovasz local lemma, we almost immediately have the following theorem for the satisfiability of exact--CNF with bounded degree.
Theorem - Let be an exact--CNF formula with maximum degree . If then is always satisfiable.
Proof. Let be Boolean random variables sampled uniformly and independently from . We are going to show that is satisfied by this random assignment with positive probability. Due to the probabilistic method, this will prove the existence of a satisfying assignment for .
Suppose there are clauses in . Let denote the bad event that is not satisfied by the random assignment . Clearly, each is dependent with at most other 's. And our goal is to show that
- .
Recall that in an exact--CNF, every clause consists of exact variable, and is violated by precisely one local assignment among all possibilities. Thus the probability that is not satisfied is .
Assuming that , i.e. , by the Lovasz local lemma (symmetric case), we have
- .
The random search algorithm
The above theorem basically says that for a CNF if every individual clause is easy to satisfy and is dependent with few other clauses then the CNF should be always satisfiable. However, the theorem only states the existence of a satisfying solution, but does not specify a way to find this solution. Next we give a simple randomized algorithm and prove it can find the satisfying solution efficiently under a slightly stronger assumption than the Lovasz local lemma.
Given as input a CNF formula defined on Boolean variables , recall that for a clause in a CNF , we use to denote the set of variables on which is defined.
The following algorithm is due to Moser in 2009. The algorithm consists of two components: the main function Solve() and a sub-routine Fix().
Solve(CNF ) - Pick values of uniformly and independently at random;
- While there is an unsatisfied clause in
- Fix();
The sub-routine Fix() is a recursive procedure:
Fix(Clause ) - Replace the values of variables in with new uniform and independent random values;
- While there is unsatisfied clause (including itself) that
- Fix();
It is an amazing discovery that this simple algorithm works well as long as the condition of Lovasz local lemma is satisfied. Here we prove a slightly weaker statement for the convenience of analysis.
Theorem - Let be an exact--CNF formula with maximum degree .
- There is a such that if then the algorithm Solve() finds a satisfying assignment for in time with high probability.
Note that in the Lovasz local lemma, the above is . So this theorem archives asymptotically the same bound as the Lovasz local lemma.
The analysis is based on a technique called entropy compression. This is a very clever idea and may be very different from what you might have seen so far about algorithm analysis. We first give a high-level description of this idea:
- We use to abstractly denote an algorithm running on an input with random bits . For an algorithm with no access to the random bits , once the input is fixed, the behavior of the algorithm as well as its output is deterministic. But for randomized algorithms, the behavior of is a random variable even when the input is fixed.
- Fix an arbitrary (worst-case) input . We try to construct a succinct representation of the behavior of in such a manner that the random bits can always be fully recovered from this succinct representation . In other words, gives an encoding (a 1-1 mapping) of the random bits to a succinct representation .
- It is a fundamental law that random bits cannot be compressed significantly by any encoding. Therefore if a longer running time of would imply that the random bits can be encoded to a succinct representation which is much shorter than , then we prove the running time of the algorithm cannot be too long.
- A natural way to reach this last contradiction is to have the following situation: As the running time of grows, naturally both lengths of random bits and the succinct representation of the behavior of grow. So if the former grows much faster than the latter as the running time grows, then a large running time may cause the length of significantly greater than the length of .
We now proceed to the analysis of and prove the above theorem.
From now on we assume that the input instance is an arbitrarily fixed exact--CNF formula with maximum degree :
- Let denote the total number of time the function is being called (including both the calls in and the recursive calls).
- Let .
Note that and are random variables which depend solely on the random bits used by the algorithm (after the input being fixed). We are going to show that with high probability, which means with high probability.
The reason we consider is that we are not sure whether is finite or infinite, so we "truncate" if it becomes too large. This truncation threshold is quite arbitrary as long as it is significantly greater than .
We start by making the following simple observations:
- A clause in will be satisfied after Fix() returned and will remain as being satisfied afterwards.
- At the moment a Fix() being called, the clause must be unsatisfied.
Proposition - There are at most top-level callings to Fix(), where is the total number of clauses in .
- If a Fix() is being called, the values of variables in are uniquely determined.
We consider a restrictive case.
Let be a set of mutually independent random variables which assume boolean values. Each event is an AND of at most literals ( or ). Let be the set of the variables that depends on. The probability that none of the bad events occurs is
In this particular model, the dependency graph is defined as that iff .
Observe that is a clause (OR of literals). Thus, is a -CNF, the CNF that each clause depends on variables. The probability
means that the the -CNF is satisfiable.
The satisfiability of -CNF is a hard problem. In particular, 3SAT (the satisfiability of 3-CNF) is the first NP-complete problem (the Cook-Levin theorem). Given the current suspect on NP vs P, we do not expect to solve this problem generally.
However, the condition of the Lovasz local lemma has an extra assumption on the degree of dependency graph. In our model, this means that each clause shares variables with at most other clauses. We call a -CNF with this property a -CNF with bounded degree .
Therefore, proving the Lovasz local lemma on the restricted forms of events as described above, can be reduced to the following problem:
- Problem
- Find a condition on and , such that any -CNF with bounded degree is satisfiable.
In 2009, Moser comes up with the following procedure solving the problem. He later generalizes the procedure to general forms of events. This not only gives a beautiful constructive proof to the Lovasz local lemma, but also provides an efficient randomized algorithm for finding a satisfiable assignment for a number of events with bounded dependencies.
Let be a -CNF of clauses with bounded degree , defined on variables . The following procedure find a satisfiable assignment for .
Solve() - Pick a random assignment of .
- While there is an unsatisfied clause in
- Fix().
The sub-routine Fix is defined as follows:
Fix() - Replace the variables in with new random values.
- While there is unsatisfied clause that
- Fix().
The procedure looks very simple. It just recursively fixes the unsatisfied clauses by randomly replacing the assignment to the variables.
We then prove it works.
Number of top-level callings of Fix
In Solve(), the subroutine Fix() is called. We now upper bound the number of times it is called (not including the recursive calls).
Assume Fix() always terminates.
- Observation
- Every clause that was satisfied before Fix() was called will still remain satisfied and will also be satisfied after Fix() returns.
The observation can be proved by induction on the structure of recursion. Since there are clauses, Solve() makes at most calls to Fix.
We then prove that Fix() terminates.
Termination of Fix
The idea of the proof is to reconstruct a random string.
Suppose that during the running of Solve(), the Fix subroutine is called for times (including all the recursive calls).
Let be the sequence of the random bits used by Solve(). It is easy to see that the length of is , because the initial random assignment of variables takes bits, and each time of calling Fix takes bits.
We then reconstruct in an alternative way.
Recall that Solve() calls Fix() at top-level for at most times. Each calling of Fix() defines a recursion tree, rooted at clause , and each node corresponds to a clause (not necessarily distinct, since a clause might be fixed for several times). Therefore, the entire running history of Solve() can be described by at most recursion trees.
- Observation 1
- Fix a . The recursion trees which capture the total running history of Solve() can be encoded in bits.
Each root node corresponds to a clause. There are clauses in . The root nodes can be represented in bits.
The smart part is how to encode the branches of the tree. Note that Fix() will call Fix() only for the that shares variables with . For a k-CNF with bounded degree , each clause can share variables with at most many other clauses. Thus, each branch in the recursion tree can be represented in bits. There are extra bits needed to denote whether the recursion ends. So totally bits are sufficient to encode all recursion trees.
- Observation 2
- The random sequence can be encoded in bits.
With bits, the structure of all the recursion trees can be encoded. With extra bits, the final assignment of the variables is stored.
We then observe that with these information, the sequence of the random bits can be reconstructed from backwards from the final assignment.
The key step is that a clause is only fixed when it is unsatisfied (obvious), and an unsatisfied clause must have exact one assignment (a clause is OR of literals, thus has exact one unsatisfied assignment). Thus, each node in the recursion tree tells the random bits in the random sequence used in the call of the Fix corresponding to the node. Therefore, can be reconstructed from the final assignment plus at most recursion trees, which can be encoded in at most bits.
The following theorem lies in the heart of the Kolmogorov complexity. The theorem states that random sequence is incompressible.
Theorem (Kolmogorov) - For any encoding scheme , with high probability, a random sequence is encoded in at least bits.
Applying the theorem, we have that with high probability,
- .
Therefore,
In order to bound , we need
- ,
which hold for for some constant . In fact, in this case, , the running time of the procedure is bounded by a polynomial!
Back to the local lemma
We showed that for , any -CNF with bounded degree is satisfiable, and the satisfied assignment can be found within polynomial time with high probability. Now we interprete this in a language of the local lemma.
Recall that the symmetric version of the local lemma:
Theorem (The local lemma: symmetric case) - Let be a set of events, and assume that the following hold:
- for all , ;
- the maximum degree of the dependency graph for the events is , and
- .
- Then
- .
- Let be a set of events, and assume that the following hold:
Suppose the underlying probability space is a number of mutually independent uniform random boolean variables, and the evens are clauses defined on variables. Then,
thus, the condition means that
which means the Moser's procedure is asymptotically optimal on the degree of dependency.