4
$\begingroup$

The general form of the Local Lemma can be stated as follows:

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.

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:

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}$.

Here is a link to the paper where they prove this result.

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:

-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.

-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.

So the particular question is how does the parallelization introduce the logarithm into the expected number of steps taken by the parallel algorithm?

$\endgroup$

1 Answer 1

5
$\begingroup$

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$.

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)$.

$\endgroup$
3
  • $\begingroup$ I'm not seeing precisely why the last equality holds (I believe that should be inequality). However, it is not immediately clear to me why the right hand side of the sum should be $O(log X/\varepsilon)$. using geometric series, it looks like you get an $X log X/\varepsilon$ from the term with the sum. Is this not correct? $\endgroup$
    – Bill Kay
    Mar 12, 2012 at 17:04
  • $\begingroup$ @Bill: You are right, it should be an inequality. The geometric series is correct. The first term of the series is $X(1-\varepsilon)^{\log X/\varepsilon}\approx X\exp(-\log X)$. $\endgroup$
    – Boris Bukh
    Mar 12, 2012 at 18:33
  • $\begingroup$ I see it now. Thanks for your help! I was just being a little dense there. $\endgroup$
    – Bill Kay
    Mar 12, 2012 at 20:44

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.