2
$\begingroup$

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!

  • 0
    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!2012-10-12
  • 0
    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 ..."2012-10-12
  • 0
    @Bitwise:In the note, the event is some Greek letter I don't know how to typeset. Would you be able to tell?2012-10-12
  • 0
    @Tim: It's a calligraphic $\mathcal E$, which you can get using `\mathcal E`.2012-10-12
  • 0
    @joriki: About the definition, I also see it here http://books.google.com/books?id=fdrJX4w3rXQC&lpg=PA212&ots=dGCHfDkaLC&dq=dependency%20graph%20%20events&pg=PA212#v=onepage&q=dependency%20graph%20%20events&f=false. So I think it is not badly worded?2012-10-12
  • 0
    @Tim: Where do you see that definition in that book? I only see a perfectly well-worded definition in the book: "Recall that a dependency graph ... is any graph $D=(V,E)$ ..."2012-10-12
  • 0
    @joriki: Is it the difference between "a dependency graph of ..." and "the dependency graph of ..."?2012-10-12
  • 0
    @Tim: Yes, that's one major flaw in the definition in the notes, which then go on to say "Note that the dependency graph is not unique", which makes no sense at all since the use of the definite article implies that it's unique. But worse still, it says "The dependency graph is a directed graph ... if ...", i.e. the conditions are stated as conditions for the graph being a directed graph instead of conditions for the graph being a dependency graph, which is of course the intended meaning.2012-10-12
  • 0
    I just realized that in the left graph $\mathcal{E}_2$ appears twice.2012-10-12
  • 0
    @Bitwise: The low-right one should be $\mathcal E_3$.2012-10-12

0 Answers 0