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

pairMarkov -- pairwise Markov statements for a graph or a directed graph

Synopsis

Description

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 => {b, e}}
           b => {a, c}
           c => {b, d}
           d => {c, e}
           e => {a, d}

o1 : Graph
 
i2 : pairMarkov G

o2 = {{{a}, {c}, {d, e, b}}, {{c}, {e}, {d, a, b}}, {{b}, {d}, {c, a, e}},
     ------------------------------------------------------------------------
     {{a}, {d}, {c, e, b}}, {{b}, {e}, {c, d, a}}}

o2 : List

Given a directed acyclic 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 \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 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 => {2, 3}}
             2 => {4, 5}
             3 => {5, 6}
             4 => {7}
             5 => {7}
             6 => {7}
             7 => {}

o3 : Digraph
 
i4 : netList pack (3, pairMarkov D)

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

See also

Ways to use pairMarkov :

For the programmer

The object pairMarkov is a method function.