Mutual independence in the Local Lemma

100 Views Asked by At

The statement of the local lemma relies on dependency graphs.

Given events $A_1, \dots A_n$ a dependency graph $G = ([n], E)$ on the $A_i$ satisfies that for all $i$, we have that $A_i$ is mutually independent of $\{A_j : \{i, j\} \not\in E\}$

What exactly does this mutual independence assumption mean on a set of events? For instance, say we have $A_1$ and $\{A_2, A_3\}$. Does this mean that $A_1, A_2, A_3$ are mutually independent or something slightly different?

1

There are 1 best solutions below

0
On BEST ANSWER

The traditional mutual independence assumption is that conditioning on any combination of the $A_j$ and their negations does not change the probability of $A_i$. Formally, if $S,T \subseteq \{j : ij \notin E\}$, then we want $$ \Pr\left[A_i \,\middle|\, \left(\bigwedge_{j \in S} A_j\right) \land \left(\bigwedge_{j \in T} \neg A_j\right) \right] = \Pr[A_i]. $$ I'm pretty sure this is equivalent to asking that $\{A_i\} \cup \{A_j : ij \notin E\}$ are mutually independent.

The typical thing to watch out for is events which are related to but pairwise independent from $A_i$, because they can still affect the probability of $A_i$ when we combine several of them.

For example, take a triangle graph on vertices $\{1,2,3\}$ and give it a random red-blue vertex coloring; let $A_{ij}$ be the event that vertices $i$ and $j$ get the same coloring. Then any two of these events are independent. However, $\Pr[A_{12}] = \frac12$ while $\Pr[A_{12} \mid A_{13} \land A_{23}] = 1$. (Similarly, $\Pr[A_{12} \mid \neg A_{13} \land \neg A_{23}] = 1$: the negations don't help.) So we do need edges in the dependency graph. (At least two of them.)

We're definitely fine in the common setting where we choose random variables $(X_1, X_2, \dots, X_N)$, have each event $A_i$ be determined by a subset of these random variables, and put an edge $ij$ in the dependency graph whenever $A_i$ and $A_j$ share some of the random variables that they're determined by.


It's also been observed (by Erdős and Spencer in 1990, in their paper Lopsided Lovász Local Lemma and Latin transversals) that the condition we actually use in the proof of the local lemma is weaker, and we can make use of this. Specifically, what we really want is a "lopsidependency graph" $G$ satisfying the property that $$ \Pr\left[A_i \,\middle|\, \bigwedge_{j \in S} \neg A_j \right] \le \Pr[A_i] $$ for any $i, S$ such that $ij \notin E(G)$ for all $j \in S$.