1
$\begingroup$

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\}$.

  • 0
    @Tim For me, a dependency graph has undirected edges and a dependency digraph has directed ones. I picked up this terminology from http://arxiv.org/abs/0905.3983.2012-10-12

1 Answers 1

2

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.