Can you explain the description of the Lovasz Local Lemma by Moser+Tardos? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T00:43:39Z http://mathoverflow.net/feeds/question/35860 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35860/can-you-explain-the-description-of-the-lovasz-local-lemma-by-mosertardos Can you explain the description of the Lovasz Local Lemma by Moser+Tardos? Niel de Beaudrap 2010-08-17T12:08:13Z 2010-08-17T21:12:15Z <p>The Lov&aacute;sz Local Lemma (or <strong>LLL</strong>) concerns itself with the probability of avoiding a collection of "bad" events <strong>A</strong>, given that the set of events is "nearly independent" (each bad event <em>A</em>&nbsp;&isin;&nbsp;<strong>A</strong> has probability which is bounded above in terms of the number of other events <em>A</em>', <em>A</em>'', 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 <a href="http://www.cs.elte.hu/~lovasz/scans/LocalLem.pdf" rel="nofollow">this pdf</a> (the link to which can be found on <a href="http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma#References" rel="nofollow">Wikipedia's page on the LLL</a>); several other papers present it in a similar fashion.</p> <p>In the article [<a href="http://www.arxiv.org/abs/0903.0544" rel="nofollow">arXiv:0903.0544</a>], 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:</p> <blockquote> <p><strong>Theorem.</strong> Let <strong>A</strong> be a finite set of events in a probability space. For <em>A</em>&nbsp;&isin;&nbsp;<strong>A</strong> let &Gamma;(<em>A</em>) be a subset of <strong>A</strong> satisfying that <em>A</em> is independent from the collection of events <strong>A</strong>&nbsp;\&nbsp;({<em>A</em>}&nbsp;&cup;&nbsp;&Gamma;(<em>A</em>)). If there exists an assignment of reals x&nbsp;:&nbsp;<strong>A</strong>&nbsp;→&nbsp;(0,1) such that $$\forall A \in \mathbf A : \Pr[A] \;\leqslant\; \mathrm x(A) \prod_{B \in \Gamma(A)} (1-\mathrm x(B))$$</p> <p>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.</p> </blockquote> <p>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 &Gamma;(<em>A</em>) in the bounding condition "wants to be" a bound on the conditional probabilities for events <em>A</em>, 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?</p> http://mathoverflow.net/questions/35860/can-you-explain-the-description-of-the-lovasz-local-lemma-by-mosertardos/35867#35867 Answer by James Martin for Can you explain the description of the Lovasz Local Lemma by Moser+Tardos? James Martin 2010-08-17T13:15:14Z 2010-08-17T13:15:14Z <p>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". </p> <p>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$).</p> <p>Then the condition $P(A) \leq 1/(4d)$ in the symmetric form implies the condition</p> <p>$P(A) \leq x(A) \prod_{B\in\Gamma(A)} (1-x(B))$ </p> <p>which is the hypothesis of the general form. </p> <p>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! </p> http://mathoverflow.net/questions/35860/can-you-explain-the-description-of-the-lovasz-local-lemma-by-mosertardos/35881#35881 Answer by Didier Piau for Can you explain the description of the Lovasz Local Lemma by Moser+Tardos? Didier Piau 2010-08-17T15:49:53Z 2010-08-17T21:12:15Z <p>Yes, one can prove the refinement stated in your question by a slight adaptation of the proof of the classical case. </p> <p>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}=$<code>{</code>A<code>}</code>$\cup$<code>{</code>$A_i;1\le i\le n$<code>}</code>, where $B$ denotes the union of the events $A_i$ for $1\le i\le n$ and $\bar B$ denotes the complement of $B$. </p> <p>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})$.</p> <p>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$.</p> <p>Some additional work is required to deal with the denumerator. Assume wlog that $\Gamma(A)=$<code>{</code>$A_i;1\le i\le q$<code>}</code> 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 <code>{</code>$A_i;1\le i\le n$<code>}</code>.</p> <p>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.</p>