# Understanding dependency graph for a set of events

Deﬁnition 4. Let $\mathcal{E}_1 , \mathcal{E}_2 , \dots, \mathcal{E}_n$ be n events on a probability space $Ω$. The dependency graph is a directed graph $D = (V, E)$ on the set of vertices $V = {1, \dots , n}$ (corresponding to $\mathcal{E}_1 , \mathcal{E}_2 , \dots, \mathcal{E}_n$ ) if for each $1 ≤ i ≤ n, \mathcal{E}_i$ is mutually independent of all the events $\{\mathcal{E}_j : (i, j) \notin E\}$.

1. Note that the dependency graph is not unique. For instance, consider two independent coin ﬂips with outcome H or T. Consider the events

$$\mathcal{E}_1 := \{(H, H), (H, T )\} \text{ (ﬁrst coin ﬂip is H)},$$

$$\mathcal{E}_2 := \{(H, H), (T, H)\} \text{ (second coin ﬂip is H)},$$

$$\mathcal{E}_3 := \{(H, H), (T, T )\} \text{ (both coin ﬂips are the same)}.$$

Then, two possible dependency graphs are as follows(for the left graph, the low-right vertex should be $\mathcal E_3$.): In the example, if I am correct, the three events $\mathcal{E}_1, \mathcal{E}_2, \mathcal{E}_3$ are pairwise independent but not mutually independent. But the first dependency graph shows that $\mathcal{E}_1$ is mutually independent of $\mathcal{E}_3$, $\mathcal{E}_2$ is mutually independent of $\mathcal{E}_1$, and $\mathcal{E}_3$ is mutually independent of $\mathcal{E}_2$. The second dependency graph shows that $\mathcal{E}_1$ is mutually independent of $\mathcal{E}_3$, $\mathcal{E}_3$ is mutually independent of $\mathcal{E}_1$, and $\mathcal{E}_2$ is mutually independent of $\mathcal{E}_1$.

• So it seems like a dependency graph of a set of events doesn't necessarily need to capture all the dependence or independence relation between events?
• In a dependency graph of a set of events, does existence of an edge from $A_i$ to $A_j$ imply that $A_i$ is not mutually independent of $A_j$? I think no, because in the example, the three events are pairwise independent, but there are edges between some two of them.

• Is the concept an event being mutually independent of another event not a symmetric relation between events? Our usual definition for mutual independence between two events are $P(\mathcal{E}_1 \cap \mathcal{E}_2) = P(\mathcal{E}_1) P(\mathcal{E}_2)$, which seems to be a symmetric relation between events.

2. More generally, any directed graph with minimum out degree 1 is a dependency graph.

If all events $\mathcal{E}_1 , \mathcal{E}_2 , \dots, \mathcal{E}_n$ are mutually independent, then the empty graph is a dependency graph.

Why is a directed graph with "minimum out degree 1" singled out in particular?

Thanks and regards!

• Do you mind changing the notation of E, since you gave it as a name for both the edges and the vertices, which is confusing (and it doesn't match the figure, which uses epsilon)... thanks! Oct 12, 2012 at 14:02
• That definition is very badly worded; I wouldn't take it too seriously. What I think it's trying to say is "A directed graph $D=(V,E)$ is called a dependency graph if ..." Oct 12, 2012 at 14:03
• @Bitwise:In the note, the event is some Greek letter I don't know how to typeset. Would you be able to tell?
– Tim
Oct 12, 2012 at 14:04
• @Tim: It's a calligraphic $\mathcal E$, which you can get using \mathcal E. Oct 12, 2012 at 14:05
• @joriki: About the definition, I also see it here books.google.com/…. So I think it is not badly worded?
– Tim
Oct 12, 2012 at 14:06