Belief Network, or directed acyclic graphical model (DAG).
When BN is huge:
Exact Inference(variable elimination)
Stochastic Inference(MCMC)

Dependence

Samples are dependent, form Markov Chain.
Converge to real distribution, when all p > 0.
Methods to improve convergence:
– Blocking
– Rao-Blackwellised
In each sample, variables are all dependent.
9 variables, binary states.
Parallel Computing the same colour ones. Sequentially: MRF: divided into collections of variables (???)
Problem of Synchronous Gibbs:
Strong positive correlation at the start.
——Sequential Execution shows a strong positive correlation
——Parallel Execution shows a strong negative correlation
Conclusion is that: Adjacent variables cannot be sampled simultaneously.
Chromatic Sampler (色度采样)
For models with weak dependencies.
k-coloring of the graphical model 9 variables (means a part form a huge image), each vertex only depends on the peers (left, right, up, down)
So two threads start simultanously: from red and blue.
sequential consistency (顺序一致性)
Synchronous Gibbs Sampler
Fortunately, the parallel computing community has developed methods to directly transform sequential graph algorithms into equivalent parallel graph algorithms using graph colorings. 
The algo provided by :  So in the MRF, all of the vertexes(variables) can be divided into two groups, as marked as two colors.
From this point of view, given k colors (states), we believe that in the same group, simutaiously we can flip a coin at each vertex.
I think it is like a pre-processing, which guarentees all variables within a color are conditionally independent given the variables in the remaining colors and can therefore be sampled independently and in parallel.
Ergodic Markov Chain
Markov Chain discretes in time and states. If we say at time u, the MC is in state i, but when it is in time t+u, the state is in j, and the transition probability and process are not depend on time u, then we say it is an ergodic MC.
p ij represents the prob of i to j, then pij = P { xn+1 = j  |  xn = i } , i,j=0,1,2,…
So we can have a transition matrix: Splash Gibbs Sampler 