Sign up ×
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.

Definition 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 flips with outcome H or T. Consider the events

    $$\mathcal{E}_1 := \{(H, H), (H, T )\} \text{ (first coin flip is H)},$$

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

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

    Then, two possible dependency graphs are as follows(for the left graph, the low-right vertex should be $\mathcal E_3$.):
    enter image description here

    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!

share|cite|improve this question
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! – Bitwise Oct 12 '12 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 ..." – joriki Oct 12 '12 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 '12 at 14:04
@Tim: It's a calligraphic $\mathcal E$, which you can get using \mathcal E. – joriki Oct 12 '12 at 14:05
@joriki: About the definition, I also see it here…. So I think it is not badly worded? – Tim Oct 12 '12 at 14:06

Your Answer


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

Browse other questions tagged or ask your own question.