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

## Synopsis

• Usage:
globalMarkov G
• Inputs:
• G, an instance of the type Graph or an instance of the type Digraph
• Outputs:
• a list, whose entries are triples {A,B,C} representing global Markov conditional independence statements of the form A is independent of B given C'' that hold for G.

## 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

• localMarkov -- local Markov statements for a graph or a directed graph
• pairMarkov -- pairwise Markov statements for a graph or a directed graph

## Ways to use globalMarkov :

• "globalMarkov(Digraph)"
• "globalMarkov(Graph)"

## For the programmer

The object globalMarkov is .