Macaulay2 » Documentation
Packages » GraphicalModels :: globalMarkov
next | previous | forward | backward | up | index | toc

globalMarkov -- global Markov statements for a graph or a directed graph

Synopsis

Description

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 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}}|{{2, 4}, {3, 6}, {1}}      |{{1, 3}, {4, 7}, {5, 6, 2}}|
     +---------------------------+---------------------------+---------------------------+
     |{{1, 6}, {4, 5}, {2, 3}}   |{{1, 4}, {5, 6}, {2, 3}}   |{{1, 5}, {4, 6}, {2, 3}}   |
     +---------------------------+---------------------------+---------------------------+
     |{{1, 2}, {6, 7}, {4, 5, 3}}|{{1, 2, 4, 5}, {6}, {3}}   |{{1, 3, 5, 6}, {4}, {2}}   |
     +---------------------------+---------------------------+---------------------------+
     |{{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.

Caveat

See also

Ways to use globalMarkov:

For the programmer

The object globalMarkov is a method function.