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}, {d, e}, {c, a}}, {{b, c}, {e}, {d, a}}, ------------------------------------------------------------------------ {{a, b}, {d}, {c, e}}, {{a, e}, {c}, {d, b}}} o2 : List |
Given a directed acyclic 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$).\break
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 \to 2, 1 \to 3, 2 \to 4, 2 \to 5, 3 \to 5, 3 \to 6, 4 \to 7, 5 \to 7$, and $6\to 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, 4}, {5, 6}, {2, 3}}|{{1, 6}, {4, 5}, {2, 3}} | +---------------------------+------------------------+---------------------------+ |{{1, 3}, {4, 7}, {5, 6, 2}}|{{1, 5}, {4, 6}, {2, 3}}|{{1, 2, 4, 5}, {6}, {3}} | +---------------------------+------------------------+---------------------------+ |{{2, 4}, {3, 6}, {1}} |{{1, 3, 5, 6}, {4}, {2}}|{{1, 2}, {6, 7}, {4, 5, 3}}| +---------------------------+------------------------+---------------------------+ |{{1, 2, 3}, {7}, {4, 5, 6}}|{{1, 4, 6}, {5}, {2, 3}}| | +---------------------------+------------------------+---------------------------+ |
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.
The object globalMarkov is a method function.