4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ The <a href="en.wikipedia.org/wiki/… Theorem</a>? $\endgroup$ – Anthony Quas May 2 '14 at 20:18
  • $\begingroup$ 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. $\endgroup$ – Vladimir May 3 '14 at 13:42
1
$\begingroup$

src: http://web.engr.illinois.edu/~swoh/courses/IE598/handout/markov.pdf

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.