Given an undirected graph $G$, a local Markov statement is of the form \{$v$, non-neighbours($v$), neighbours($v$)\} . That is, every vertex $v$ of $G$ is independent of its non-neighbours given its neighbours.
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 local 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 : localMarkov G
o2 = {{{a}, {c, d}, {e, b}}, {{a, b}, {d}, {c, e}}, {{b, c}, {e}, {d, a}},
------------------------------------------------------------------------
{{b}, {d, e}, {c, a}}, {{a, e}, {c}, {d, b}}}
o2 : List
|
Given a directed acyclic graph $G$, local Markov statements are of the form \{$v$, nondescendents($v$) - parents($v$), parents($v$)\} . In other words, every vertex $v$ of $G$ is independent of its nondescendents (excluding parents) given its parents.
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 local 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, localMarkov D)
+---------------------------+------------------------+------------------------+
o4 = |{{1, 3, 5, 6}, {4}, {2}} |{{1, 2, 4, 5}, {6}, {3}}|{{1, 4, 6}, {5}, {2, 3}}|
+---------------------------+------------------------+------------------------+
|{{1, 2, 3}, {7}, {4, 5, 6}}|{{2}, {3, 6}, {1}} |{{2, 4}, {3}, {1}} |
+---------------------------+------------------------+------------------------+
|
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 localMarkov is a method function.