<p>The <a href="http://www.sciencedirect.com/science/article/pii/0166218X91900404" rel="nofollow">Lopsided Lovasz Local Lemma</a> relaxes the mutual independence condition to negative dependence. We assume we have events $A_1, \ldots, A_n$, with a lopsidependency graph $G$ defined on $[n]$ s.t. for every event $A_i$ and every $S \subseteq [n] \setminus \Gamma^+(i)$, 
$$
\Pr\left(A_i \mid \bigwedge_{j \in S}{\bar{A_j}}\right) \le \Pr(A_i).
$$
As you (sort of) suggest, the classical inductive proof of LLL works fine with the lopsidependency graph in place of the depdendency graph. This answers your question because the negative dependence condition is only weaker than the equality you wrote. See these <a href="http://theory.stanford.edu/~jvondrak/MATH233/Math233-lec04.pdf" rel="nofollow">notes by Vondrak</a> for some applications.</p>

<p>The tightness of the constant $e$ (in the limit) was shown by <a href="http://link.springer.com/article/10.1007/BF02579368" rel="nofollow">Shearer</a>, who characterized the smallest probabilities that guarantee a local lemma-type statement for any given dependency graph. There are fascinating connections with statistical mechanics, covered in a paper of <a href="https://people.maths.ox.ac.uk/scott/Papers/lllshort.pdf" rel="nofollow">Scott and Sokal</a>.</p>

CC BY-SA 3.0
2016-07-23T23:03:51.340Z
2016-07-26T09:02:24.863Z
2016-07-26T09:02:24.863Z
Sasho Nikolov
<p>The formulation on p.70 of the 4th edition of <em>The Probabilistic Method</em> by Alon and Spencer is along the lines you state.</p>

CC BY-SA 3.0
2016-07-22T04:13:28.790Z
2016-07-22T04:13:28.790Z
kodlu
<p>The Lovász local lemma, as stated in Corollary 5.1.2 <a href="http://nguyen.hong.hai.free.fr/EBOOKS/SCIENCE%20AND%20ENGINEERING/MATHEMATIQUE/PROBABILITY/The_Probabilistic_Method.pdf">here</a>, is given as follows.</p>

<blockquote>
  <p><strong>Lemma.</strong> Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is <em>mutually independent</em> of all but at most $d$ of the $A_j$'s. Then if $ep(d+1) \leq 1$, the probability that none of the $A_i$'s occur is positive.</p>
</blockquote>

<p>I have a few questions about the assumptions needed for the above lemma. Looking at the proof given in the Wikipedia article <a href="https://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma">here</a>, it appears that one does <em>not</em> require each $A_i$ to be mutually independent of all but at most $d$ of the $A_j$'s. Instead, all one requires is that$$\text{Prob}\left(A_i \mid \bigwedge_{j \in S} \overline{B_j} \right) = \text{Prob}(A_i),$$where $S = \{1, \ldots, k\} - \Gamma(A_i)$, where $\Gamma(A_i)$ is the dependency locus of $A_i$. I think that the above condition appears to be considerably weaker than mutual independence; indeed, mutual independence means that
$$\text{Prob}\left(A_i \wedge \bigwedge_{j \in S} \overline{B_j}\right) = \text{Prob}(A_i) \cdot \prod_{j \in S} \text{Prob}(\overline{B_j}).$$</p>

<p>Am I right to say that mutual independence is not required?</p>

<p>Also, is there a reason why the constant $e$ in the statement of the Lovász local lemma is optimal? Several sources seem to agree on this. It seems somewhat arbitrary to me, and I feel like a smaller constant can be achieved by being more careful in the proof.</p>

<p>Thanks in advance!</p>

<co.combinatorics><pr.probability>
Can the "mutual independence" condition in the Lovász local lemma be weakened?
user2503162
# Can the "mutual independence" condition in the Lovász local lemma be weakened?

(Asked by: username_0 on 2016-07-20)

The Lovász local lemma, as stated in Corollary 5.1.2 [here](http://nguyen.hong.hai.free.fr/EBOOKS/SCIENCE%20AND%20ENGINEERING/MATHEMATIQUE/PROBABILITY/The_Probabilistic_Method.pdf), is given as follows.

> **Lemma.** Let $A\_1, \ldots, A\_k$ be events such that each $A\_i$ has probability at most $p$ and such that each $A\_i$ is *mutually independent* of all but at most $d$ of the $A\_j$'s. Then if $ep(d+1) \leq 1$, the probability that none of the $A\_i$'s occur is positive.

I have a few questions about the assumptions needed for the above lemma. Looking at the proof given in the Wikipedia article [here](https://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma), it appears that one does *not* require each $A\_i$ to be mutually independent of all but at most $d$ of the $A\_j$'s. Instead, all one requires is that$$\text{Prob}\left(A\_i \mid \bigwedge\_{j \in S} \overline{B\_j} \right) = \text{Prob}(A\_i),$$where $S = \{1, \ldots, k\} - \Gamma(A\_i)$, where $\Gamma(A\_i)$ is the dependency locus of $A\_i$. I think that the above condition appears to be considerably weaker than mutual independence; indeed, mutual independence means that
$$\text{Prob}\left(A\_i \wedge \bigwedge\_{j \in S} \overline{B\_j}\right) = \text{Prob}(A\_i) \cdot \prod\_{j \in S} \text{Prob}(\overline{B\_j}).$$

Am I right to say that mutual independence is not required?

Also, is there a reason why the constant $e$ in the statement of the Lovász local lemma is optimal? Several sources seem to agree on this. It seems somewhat arbitrary to me, and I feel like a smaller constant can be achieved by being more careful in the proof.

Thanks in advance!

**Tags:** co.combinatorics, pr.probability


---

## 2 answers

### Answer by username_1 on 2016-07-23. Score: 8

The [Lopsided Lovasz Local Lemma](http://www.sciencedirect.com/science/article/pii/0166218X91900404) relaxes the mutual independence condition to negative dependence. We assume we have events $A\_1, \ldots, A\_n$, with a lopsidependency graph $G$ defined on $[n]$ s.t. for every event $A\_i$ and every $S \subseteq [n] \setminus \Gamma^+(i)$,
$$
\Pr\left(A\_i \mid \bigwedge\_{j \in S}{\bar{A\_j}}\right) \le \Pr(A\_i).
$$
As you (sort of) suggest, the classical inductive proof of LLL works fine with the lopsidependency graph in place of the depdendency graph. This answers your question because the negative dependence condition is only weaker than the equality you wrote. See these [notes by Vondrak](http://theory.stanford.edu/~jvondrak/MATH233/Math233-lec04.pdf) for some applications.

The tightness of the constant $e$ (in the limit) was shown by [Shearer](http://link.springer.com/article/10.1007/BF02579368), who characterized the smallest probabilities that guarantee a local lemma-type statement for any given dependency graph. There are fascinating connections with statistical mechanics, covered in a paper of [Scott and Sokal](https://people.maths.ox.ac.uk/scott/Papers/lllshort.pdf).


---

### Answer by username_2 on 2016-07-22. Score: 6

The formulation on p.70 of the 4th edition of *The Probabilistic Method* by Alon and Spencer is along the lines you state.


---

