Proof: Let be a positive distribution defined by a Markov network where are the adjacencies of , . Construct a consistent dependency network from by extracting the conditional distributions . Because these probabilities came from the Markov network, we know that so that the adjacencies in the dependency-network structure are the same as those in the Markov network. Now let be a positive distribution encoded by a consistent dependency network. By definition, we have that is independent of given , . Because is positive and these independencies comprise the global Markov property of a Markov network with , , the Hammersley-Clifford theorem (Besag, 1974; Lauritzen, Dawid, Larsen, and Leimer, 1990) implies that can be represented by this Markov network.
Theorem 2: An ordered Gibbs sampler applied to a consistent dependency network for , where each is finite (and hence discrete) and each local distribution is positive, defines a Markov chain with a unique stationary joint distribution for equal to that can be reached from any initial state of the chain.
Proof: In the body of the paper, we showed that the Markov chain can be described by the transition matrix , where is the ``local'' transition matrix describing the resampling of according to the local distribution . We also showed that this Markov chain has a unique joint distribution that can be reached from any starting point. Here, we show that is that stationary distribution--that is, , where . To do so, we show that for each , .
Theorem 4: A minimal consistent dependency network for a positive distribution must be bi-directional.
Proof: We use the graphoid axioms of Pearl (1988). Suppose the theorem is false. Then, there exists nodes and such that is a parent of and is not a parent of . Let , , and . From minimality, we know that does not hold. By decomposition, does not hold. Given positivity, the intersection property holds. By the intersection property, at least one of the following conditions does not hold: (1) , (2) . (If , then condition 2 holds vacuously.) Now, from Theorem 2, we know that . Using weak union, we have that --that is, condition 1 holds. Also, from Theorem 2, we know that --that is, condition 2 holds, yielding a contradiction.