A requst for clarification of the analysis of the Moser-Tardos algorithmic proof of the Local Lemma - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T02:07:17Z http://mathoverflow.net/feeds/question/90067 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90067/a-requst-for-clarification-of-the-analysis-of-the-moser-tardos-algorithmic-proof A requst for clarification of the analysis of the Moser-Tardos algorithmic proof of the Local Lemma Bill Kay 2012-03-02T19:35:40Z 2012-03-03T15:33:13Z <p>The general form of the Local Lemma can be stated as follows:</p> <blockquote> <p>Let $\mathcal{A}$ be a finite set of events in a probability space. For $A \in \mathcal{A}$, let $\Gamma(A)$ be a subset of $\mathcal{A}$ such that $A$ is independent of the collection of events in $\mathcal{A} \setminus ({A} \cup \Gamma(A))$. If there exists an assignment of reals $x : \mathcal{A} \rightarrow (0,1)$ such that $\forall A \in \mathcal{A}$: $$\text{Pr}(A) \leq x(A) \Pi_{B \in \Gamma(A)} (1-x(B))$$ Then the probability of avoiding all the events in $\mathcal{A}$ is positive. </p> </blockquote> <p>Recently, Moser and Tardos produced a proof of the Local Lemma which provides a random algorithm which produces the point in the probability space which avoids all the events in $\mathcal{A}$, and under the hypotheses of the lemma has fast expected runtime. In the same paper, they provide a parallel algorithm and the following theorem:</p> <blockquote> <p>Let $\mathcal{P}$ be a finite set of mutually independent random variables in a probability space. and let $\mathcal{A}$ be a finite set of events determined by $\mathcal{P}$. Let $\varepsilon >0$. If there exists an assignment of reals $x : \mathcal{A} \rightarrow (0,1)$ such that $\forall A \in \mathcal{A}$: $$\text{Pr}(A) \leq(1 - \varepsilon) x(A) \Pi_{B \in \Gamma(A)} (1-x(B))$$ then the parallel algorithm takes an expected $O(\frac{1}{\varepsilon}$ log $\sum_{A \in \mathcal{A}}$ $\frac{x(A)}{1-x(A)})$ steps before it finds an evaluation of the variables in $\mathcal{P}$ which violates no variable in $\mathcal{A}$. </p> </blockquote> <p>Here is a <a href="http://arxiv.org/pdf/0903.0544v3.pdf" rel="nofollow">link</a> to the paper where they prove this result. </p> <p>I am working through the analysis of the parallel algorithm, and I appear to have hit a snag. At the bottom of page 7 in the linked paper, the authors introduce $Q(k)$, the probability that the algorithm takes at least $k$ steps. Then the bound $$Q(k) \leq (1-\varepsilon)^k \sum_{A \in \mathcal{A}} \frac{x(A)}{1-x(A)}$$ is established. This is the point where I get a little lost. The claim is that the theorem follows easily from this bound. If someone could help me see how the theorem follows from the bound, that would be quite helpful! I have noted a few points that I believe are key:</p> <p>-This probability $Q(k)$ seems to not actually be the probability that the parallel algorithm takes at least $k$ steps. Instead, it seems to be the probability that the sequential algorithm takes at least $k$ steps if we view the parallel algorithm as an instance of the sequential algorithm. This is explained in the opening paragraph of section 4.</p> <p>-If $Q(k)$ is the probability that the sequential algorithm takes at least $k$ steps, then $Q(k) - Q(k+1)$ is the probability that the algorithm takes exactly $k$ steps. Taking expectation, we get that the expected number of steps is $\sum_{k = 1}^\infty kQ(k) - kQ(k+1)$. This sum telescopes leaving us with $\sum_{k = 1}^\infty Q(k)$. Applying the bound on $Q(k)$ we see that the expectation here is upper bounded by $O(\frac{1}{\varepsilon} \sum_{A \in \mathcal{A}} \frac{x(A)}{1-x(A)})$. Somehow, the "parallelization" of this algorithm gets that log in the desired claim. </p> <p>So the particular question is how does the parallelization introduce the logarithm into the expected number of steps taken by the parallel algorithm? </p> http://mathoverflow.net/questions/90067/a-requst-for-clarification-of-the-analysis-of-the-moser-tardos-algorithmic-proof/90114#90114 Answer by Boris Bukh for A requst for clarification of the analysis of the Moser-Tardos algorithmic proof of the Local Lemma Boris Bukh 2012-03-03T13:28:58Z 2012-03-03T15:33:13Z <p>The reason the bound you obtain is worse than the advertised bound is that you sum over all $k$, including those $k$ for which the bound on $Q(k)$ is greater than $1$. </p> <p>Suppose $T$ is an integer-valued random variable about which we know that $\Pr[T\geq k]\leq (1-\varepsilon)^k X$. Then \begin{align*} E[T]\leq (\log X/\varepsilon) \Pr[T\geq \log X/\varepsilon] + \sum_{k\geq \log X/\varepsilon} \Pr[T\geq k] =(\log X/\varepsilon)+X\sum_{k\geq \log X/\varepsilon}(1-\varepsilon)^k \end{align*} which is $O(\log X/\varepsilon)$.</p>