4
$\begingroup$

The Lovász Local Lemma (or LLL) concerns itself with the probability of avoiding a collection of "bad" events A, given that the set of events is "nearly independent" (each bad event A ∈ A has probability which is bounded above in terms of the number of other events A', A'', etc. from which it is not independent), there is a non-zero probability of avoiding all of the bad events simultaneously. The original presentation seems to be the Lemma on page 8 of this pdf (the link to which can be found on Wikipedia's page on the LLL); several other papers present it in a similar fashion.

In the article [arXiv:0903.0544], restricting to the setting where the "bad events" of the LLL are defined in terms of a probability space of independently distributed bits, Moser and Tardos present a probabilistic algorithm for sampling from the event space until an event is found which avoids all bad events, which requires at most polynomially many samples with high probability. However, their characterization of the LLL is significantly different from any presentation of it that I have seen elsewhere. Their version of the LLL is as follows:

Theorem. Let A be a finite set of events in a probability space. For A ∈ A let Γ(A) be a subset of A satisfying that A is independent from the collection of events A \ ({A} ∪ Γ(A)). If there exists an assignment of reals x : A → (0,1) such that $$ \forall A \in \mathbf A : \Pr[A] \;\leqslant\; \mathrm x(A) \prod_{B \in \Gamma(A)} (1-\mathrm x(B))$$

then the probability of avoiding all events in A is at least $\prod\limits_{A \in \mathbf A} \;(1 \;−\; \mathrm x(A))$, in particular it is positive.

The proof that their sampling algorithm works seems to depend substantially upon this presentation of the LLL, but I cannot decipher the exact relationship between this and more common presentations of it. It looks as though the product over Γ(A) in the bounding condition "wants to be" a bound on the conditional probabilities for events A, but I haven't been able to make the link. Could someone help me with the connection between this statement and more familar versions of the LLL?

$\endgroup$

2 Answers 2

8
$\begingroup$

The version of the LLL that you wrote out above is stronger than the one on page 8 of the paper you linked to. The one you link to is sometimes known as the "symmetric form" of the LLL and the one you wrote out above as the "general form".

To see that the general form implies the symmetric form: restrict to the case where $|\Gamma(A)|\leq d$ for all $A$ (as assumed in the symmetric form), and let $x(A)$ be a constant $x$ such that $x(1-x)^d \geq 1/(4d)$. (Check that you can always find such an $x$).

Then the condition $P(A) \leq 1/(4d)$ in the symmetric form implies the condition

$P(A) \leq x(A) \prod_{B\in\Gamma(A)} (1-x(B))$

which is the hypothesis of the general form.

A standard reference is Chapter 5 of the book of Alon and Spencer, "The Probabilistic Method". Of course it doesn't cover Moser's new approach!

$\endgroup$
1
  • $\begingroup$ Thanks for the clarification! I find their proof quite elegant, but could not clearly see the relation between the Moser+Tardos statement and what you describe as the "symmetric" LLL (which was the only one I had seen.) $\endgroup$ Aug 20, 2010 at 9:35
4
$\begingroup$

Yes, one can prove the refinement stated in your question by a slight adaptation of the proof of the classical case.

More precisely, the proof is by recursion over the number of events in $\mathbf{A}$. Like in the classical case, assuming that the statement holds for every collection of $n$ events, it is enough to show that $P(A|\bar{B})\le x(A)$ for every collection $\mathbf{A}=${A}$\cup${$A_i;1\le i\le n$}`, where $B$ denotes the union of the events $A_i$ for $1\le i\le n$ and $\bar B$ denotes the complement of $B$.

The first step is to decompose $B$ into $B=C\cup F$ where $C$ is the union of the events in $\Gamma(A)$ and $F$ the union of the events not in $\Gamma(A)$. Hence, $P(A|\bar{B})=P(A|\bar{C},\bar{F})=N/D$ where $N=P(A,\bar{C}|\bar{F})$ and $D=P(\bar{C}|\bar{F})$.

As regards the numerator, $N\le P(A|\bar{F})=P(A)$, where the equality stems from the fact that $A$ is independent of the $A_i$ not in $\Gamma(A)$, which define $F$.

Some additional work is required to deal with the denumerator. Assume wlog that $\Gamma(A)=${$A_i;1\le i\le q$}and write $\bar C$ as $\bar C=\bar A_1\cap \bar A_2\cap\cdots\cap \bar A_q$. Then, by Bayes formula, $P(\bar C|\bar{F})$ is the product over $1\le i\le q$ of $P(\bar A_i|\bar C_i,\bar{F})$, where each $C_i$ is the union of $A_j$ for $j\le q$, $j\ne i$. Now, each of these probabilities is conditional on an event which involves at most $q-1\le n$ events in $\mathbf A$ hence $P(\bar A_i|\bar C_i,\bar{F})\ge1-x(A_i)$ by the recursion hypothesis applied to the collection{$A_i;1\le i\le n$}`.

Finally, $N\le P(A)\le x(A)\prod_{i\le q}(1-x(A_i))$ and $D\ge\prod_{i\le q}(1-x(A_i))$ hence $P(A|\bar{B})\le x(A)$ for every collection $\mathbf A$ of size $n+1$ as above, which proves the theorem.

$\endgroup$
2
  • $\begingroup$ It isn't actually "Moser and Tardos' refinement". The general version has been around for many years already (with a proof along the lines that you decsribe - see eg the book of Alon and Spencer). What Moser and Tardos have is a striking new approach to the proof, rather information-theoretic in character - in particular, it is "constructive" in the sense that it not only guarantees that a "good outcome" exists, but also gives a method of finding a good outcome. $\endgroup$ Aug 17, 2010 at 20:57
  • $\begingroup$ @James Martin: thanks for your precision, I modified the formulation accordingly. $\endgroup$
    – Did
    Aug 17, 2010 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.