Given an undirected graph G, pairwise Markov statements are statements of the form {v, w, all other vertices} for each pair of non-adjacent vertices v and w of G.
For example, for the undirected 5-cycle graph G, that is, the graph on 5 vertices with edges a---b---c---d---e---a, we get the following pairwise Markov statements:
i1 : G = graph({{a,b},{b,c},{c,d},{d,e},{e,a}})
o1 = Graph{a => set {b, e}}
b => set {a, c}
c => set {b, d}
d => set {c, e}
e => set {a, d}
o1 : Graph
|
i2 : pairMarkov G
o2 = {{{a}, {c}, {d, e, b}}, {{b}, {e}, {c, d, a}}, {{b}, {d}, {c, e, a}},
------------------------------------------------------------------------
{{c}, {e}, {d, a, b}}, {{a}, {d}, {c, e, b}}}
o2 : List
|
Given a directed graph G, pairwise Markov statements are statements of the form {v, w, nondescendents(G,v)-w} for each vertex v of G and each non-descendent vertex w of v. In other words, for every vertex v of G and each nondescendent w of v, this method returns the statement: v is independent of w given all other nondescendents.
For example, given the digraph D on 7 vertices with edges 1 →2, 1 →3, 2 →4, 2 →5, 3 →5, 3 →6, 4 →7, 5 →7, and 6→7, we get the following pairwise Markov statements:
i3 : D = digraph {{1,{2,3}}, {2,{4,5}}, {3,{5,6}}, {4,{7}}, {5,{7}},{6,{7}},{7,{}}}
o3 = Digraph{1 => set {2, 3}}
2 => set {4, 5}
3 => set {5, 6}
4 => set {7}
5 => set {7}
6 => set {7}
7 => set {}
o3 : Digraph
|
i4 : netList pack (3, pairMarkov D)
+------------------------+---------------------------+---------------------------+
o4 = |{{2}, {6}, {1, 3}} |{{4}, {6}, {1, 2, 3, 5}} |{{2}, {6}, {1, 3, 4, 5}} |
+------------------------+---------------------------+---------------------------+
|{{3}, {4}, {1, 2}} |{{2}, {3}, {4, 1}} |{{1}, {4}, {2, 3, 5, 6}} |
+------------------------+---------------------------+---------------------------+
|{{4}, {5}, {1, 2, 3, 6}}|{{3}, {7}, {1, 2, 4, 5, 6}}|{{1}, {7}, {2, 3, 4, 5, 6}}|
+------------------------+---------------------------+---------------------------+
|{{2}, {3}, {1, 6}} |{{1}, {6}, {2, 3, 4, 5}} |{{5}, {6}, {1, 2, 3, 4}} |
+------------------------+---------------------------+---------------------------+
|{{1}, {5}, {2, 3, 4, 6}}|{{3}, {4}, {1, 2, 5, 6}} |{{2}, {7}, {1, 3, 4, 5, 6}}|
+------------------------+---------------------------+---------------------------+
|
This method displays only non-redundant statements. In general, given a set S of conditional independent statements and a statement s, then we say that s is a a redundant statement if s can be obtained from the statements in S using the semigraphoid axioms of conditional independence: symmetry, decomposition, weak union, and contraction as described in Section 1.1 of Judea Pearl, Causality: models, reasoning, and inference, Cambridge University Press. We do not use the intersection axiom since it is only valid for strictly positive probability distributions.