For $\mathcal{A} = \{ A_1, \ldots, A_n \}$, a finite set of events in the probability space $\Omega$, the condition in Lovasz local lemma is existence of an assignment $x : \mathcal{A} \rightarrow (0,1)$ such that one of the following three holds: (I wonder if the following three different ways for completing the statement of the condition are actually equivalent?)
- One note says $ \forall A \in \mathcal{A} : \Pr[A] \leq x(A) \prod_{B: (A,B) \in E(D)} (1-x(B)) $ Where $\{ A_1, \ldots, A_n \}$ have a dependency graph $D$, and $E(D)$ is the set of edges of $D$.
- Wikipedia says $ \forall A \in \mathcal{A} : \Pr[A] \leq x(A) \prod_{B \in \Gamma(A)} (1-x(B)) $ where $\Gamma(A)$ denote a subset of $\mathcal{A}$ such that $A$ is independent from the collection of events $\mathcal{A} \setminus (\{A \} \cup \Gamma(A))$.
- Another note says $ \forall A \in \mathcal{A} : \Pr[A] \leq x(A) \prod_{B \in S(A)} (1-x(B)) $ Where $S(A): = \{B \in \mathcal{A} \setminus \{A\} | A \text{ is dependent on } B \}$.
My doubts:
- The first two versions seem not quite consistent with each other, since $\Gamma(A)$ can be as big as possible, such as $\Gamma(A) = \mathcal{A}$, while the dependency graph $D$ of $\mathcal{A}$ seems to capture the unique dependency relation among members of $\mathcal{A}$?
- I am not sure about the last version either.
- Which version is the correct one?
- Given that a dependency graph for a set of events seems not necessarily need to catpure all (in)dependency relation between events (discussed in my another post), if the Wikipedia version of the Lemma is correct, is it more general than the first version? Thanks and regards!