2
$\begingroup$

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?)

  1. 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$.
  2. 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))$.
  3. 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:

  1. 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}$?
  2. I am not sure about the last version either.
  3. Which version is the correct one?
  4. 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!
  • 0
    Since you're wondering about the equivalence of various conditions, it might avoid confusion if you disambiguate the ungrammatical "the following condition hold" in the first sentence. Did you mean "conditions hold" or "condition holds"?2012-10-12
  • 0
    @joriki: I meant there are three different ways to complete the statement for the condition of LLL. So I used "condition holds" instead of "conditions hold". Let me know if it is still not clarified.2012-10-12
  • 0
    Now you've introduced a different grammatical error; "the either" doesn't make any sense. I presume you mean just "either"? But there are three conditions. so it should be "any".2012-10-12
  • 0
    How about now? $ $2012-10-12
  • 0
    There seems to be a time lag between when edits are made and when they become visible. In both cases the post appeared unchanged to me at first when you asked my opinion about the change. It still says "the either" when I reload it.2012-10-12
  • 0
    Another attempt for clarification has been made to the post. How about it now?2012-10-12
  • 0
    Looks good to me now.2012-10-12

0 Answers 0