Question about a condition of the asymmetric Lovasz Local Lemma

116 Views Asked by At

As I've gathered from numerous explanations of the asymmetric Lovasz Local Lemma (ALLL), the ALLL is a generalization of the notion that if a collection of independent events is such that each event occurs with small probability, then the probability that none of these events occurs is positive. In particular, the ALLL generalizes this notion to the case where each of these events is independent of all but a small number of other events.

Again, given that so many of the explanations of the ALLL I've read feature this intuition of the above paragraph, I was hoping that I could map this intuition onto the central condition of the ALLL, namely:

Suppose that there exist $x_i \in [0,1)$ and $\Pr[A_i] \leq x_i \prod_{(i,j) \in E} (1-x_j)$...

Where the $A_i$'s are the events and $E$ is the edge set of the dependency digraph.

How is the idea that each of the events is independent of all but a small number of other events captured by this condition? Or is this intuition only intended for the symmetric LLL?

1

There are 1 best solutions below

0
On

If there were many events that weren't independent of $A_i$, then the $\prod (1-x_j)$ term would be very small, and the condition would be very hard to satisfy (it would require $\Pr[A_j]$ to be very small).

So we could actually quantify the "a collection of unlikely and almost independent events thing" intuition: for the LLL to work, each event's probability has to be exponentially small in the number of events that depend on it.

It might also help you to have intuition for what each value $x_i$ is supposed to represent. It's meant as an upper bound for how high $\Pr[A_i]$ can get when conditioned on other events not happening. If we rewrite the condition as $$ \frac{\Pr[A_i]}{\prod_{j :(i,j) \in E} (1 - x_j)} \le x_i $$ then the left-hand side should resemble the conditional probability $$ \Pr\left[A_i \,\middle|\, \bigwedge_{j:(i,j) \in E} \neg A_j\right] $$ and this is meant to be upper-bounded by $x_i$.