Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the language of the Lovász Local Lemma, a dependency graph $G$ is one in which

  • each $i$ vertex corresponds to an event $A_i$ and
  • each event $A_i$ is mutually independent of the collection $\{A_j \mid ij \notin E(G), i \neq j\}$.

In words, each event is mutually independent of the collection of its non-neighbors in the dependency graph.

A dependency digraph is defined similarly, except the edges are directed.

Is there a simple example of events that define a dependency digraph that is not a dependency graph?

An example of such a thing would be events $A_1$, $A_2$, and $A_3$ for which $A_1$ is mutually independent of $\{A_2, A_3\}$, but $A_2$ is not mutually independent of $\{A_1, A_3\}$.

share|improve this question
    
As far as I know, a "dependency graph" is a directed graph itself. See mpi-inf.mpg.de/departments/d1/teaching/ss11/ProbMethod/files/…. Could you provide references for your definitions? –  Tim Oct 12 '12 at 13:54
    
Also see my related posts math.stackexchange.com/questions/211663/…, and math.stackexchange.com/questions/211400/… –  Tim Oct 12 '12 at 13:56
    
@Tim For me, a dependency graph has undirected edges and a dependency digraph has directed ones. I picked up this terminology from arxiv.org/abs/0905.3983. –  Austin Mohr Oct 12 '12 at 19:38

1 Answer 1

up vote 1 down vote accepted

Here is a simple example of events $A_1, A_2, A_3$ for which $A_1$ is mutually independent of $A_2$ and $A_3$, but $A_2$ is not mutually independent of $A_1$ and $A_3$:

Consider the probability space of words {001,010,011,101,110,111} where $A_i$ is the event that the $i$'th bit is 1. Then $Pr[A_1] = Pr[A_1|A_2] = Pr[A_1|A_3] = Pr[A_1|A_2 \wedge A_3] = 1/2$, but $Pr[A_2] = 2/3$ while $Pr[A_2|A_3] = 1/2$.

I've checked this but I suppose I could have made a mistake somewhere.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.