Given an undirected graph G, a global Markov statement is of the form {A, B, C}, where the subset C separates the subset A from the subset B in the graph G.
For example, for the undirected 5-cycle graph G, that is, the graph on 5 vertices with a---b---c---d---e---a, we get the following global Markov statements:
i1 : G = graph({{a,b},{b,c},{c,d},{d,e},{e,a}})
o1 = Graph{a => {b, e}}
b => {a, c}
c => {b, d}
d => {c, e}
e => {a, d}
o1 : Graph
|
i2 : globalMarkov G
o2 = {{{a}, {c, d}, {e, b}}, {{b, c}, {e}, {d, a}}, {{a, e}, {c}, {d, b}}, {{a, b}, {d}, {c, e}}, {{b}, {d, e}, {c, a}}}
o2 : List
|
Given a directed graph G, global Markov states that A is independent of B given C for every triple of sets of vertices A, B, and C, such that A and B are d-separated by C (in the graph G).
The global independent statements of a directed graph are computed using the Bayes-Ball algorithm, as described in the paper Ross D. Shachter, Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams) In Proceedings of the Fourteenth Conference in Uncertainty in Artificial Intelligence, p. 480--487, 1998.
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 global Markov statements:
i3 : D = digraph {{1,{2,3}}, {2,{4,5}}, {3,{5,6}}, {4,{7}}, {5,{7}},{6,{7}},{7,{}}}
o3 = Digraph{1 => {2, 3}}
2 => {4, 5}
3 => {5, 6}
4 => {7}
5 => {7}
6 => {7}
7 => {}
o3 : Digraph
|
i4 : netList pack (3, globalMarkov D)
+---------------------------+---------------------------+---------------------------+
o4 = |{{1}, {4, 5, 6, 7}, {2, 3}}|{{1, 3, 5, 6}, {4}, {2}} |{{1, 3}, {4, 7}, {5, 6, 2}}|
+---------------------------+---------------------------+---------------------------+
|{{1, 2, 4, 5}, {6}, {3}} |{{1, 6}, {4, 5}, {2, 3}} |{{1, 4}, {5, 6}, {2, 3}} |
+---------------------------+---------------------------+---------------------------+
|{{2, 4}, {3, 6}, {1}} |{{1, 5}, {4, 6}, {2, 3}} |{{1, 2}, {6, 7}, {4, 5, 3}}|
+---------------------------+---------------------------+---------------------------+
|{{1, 4, 6}, {5}, {2, 3}} |{{1, 2, 3}, {7}, {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.