# Local Markov implies global Markov

Let $G=(V,E)$ be a finite simple graph, and let $\{X_i\}_{i \in V}$ be a collection of random variables associated with the vertices of $G$. The joint distributions of these r.v.s is a Markov Random Field if, for any three subsets $U,W,C \subset V$ such that $C$ separates $U$ from $W$ (i.e., any path from $U$ to $W$ passes through $C$), it holds that conditioned on the r.v.s in $C$, the r.v.s in $U$ are independent from those in $W$. This is called the global Markov property. An implication is the pairwise Markov property, which states that for all $(i,j) \not \in E$, $X_i$ is independent of $X_j$, conditioned on the rest of the r.v.s.

A finite distribution over $\{X_i\}$ is called positive if every combination of assignments has positive probability (here "every" means those whose marginals are positive). I am looking for a reference for the fact that for positive distributions, the pairwise Markov property implies the global Markov property. Thanks!

• The <a href="en.wikipedia.org/wiki/… Theorem</a>? – Anthony Quas May 2 '14 at 20:18
• Anthony: (there's a mistake in your formatting) I don't see how the Hammersley Clifford theorem shows this. A condition for the theorem to apply is the global property. – Vladimir May 3 '14 at 13:42

## 1 Answer

copied below

(3) being if $x_A ⊥ x_B|(x_C, x_D)$ and $x_A ⊥ x_C|x_B ∪ x_D,$ then $x_A ⊥ (x_B, x_C)|x_D$

which always holds for positive P.

Proof of (P)$⇒$(G) when (3) holds: [Pearl,Paz 1987] by induction over s $\triangleq$ |B| when s = n − 2, (P)$⇔$(G) assume (G) for any B with |B| ≥ s and prove it for |B| = s − 1

by induction assumption $$x_C ⊥ x_A|(x_B, x_i) \\ x_C ⊥ x_i|(x_B, x_A) by (3),\\ x_C ⊥ (x_A, x_i)|x_B$$ by induction, we see that (G) holds for all sizes of B.