4
$\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!

$\endgroup$
10
  • $\begingroup$ 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! $\endgroup$
    – Bitwise
    Oct 12, 2012 at 14:02
  • $\begingroup$ 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 ..." $\endgroup$
    – joriki
    Oct 12, 2012 at 14:03
  • $\begingroup$ @Bitwise:In the note, the event is some Greek letter I don't know how to typeset. Would you be able to tell? $\endgroup$
    – Tim
    Oct 12, 2012 at 14:04
  • $\begingroup$ @Tim: It's a calligraphic $\mathcal E$, which you can get using \mathcal E. $\endgroup$
    – joriki
    Oct 12, 2012 at 14:05
  • 1
    $\begingroup$ @joriki: About the definition, I also see it here books.google.com/…. So I think it is not badly worded? $\endgroup$
    – Tim
    Oct 12, 2012 at 14:06

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .