A recursive algorithm for Markov random fields

We propose a recursive algorithm as a more useful alternative to the Brook expansion for the joint distribution of a vector of random variables when the original formulation is in terms of the corresponding full conditional distributions, as occurs for Markov random fields. Usually, in practical applications, the computational load will still be excessive but then the algorithm can be used to obtain the componentwise full conditionals of a system after marginalising over some variables or the joint distribution of subsets of the variables, conditioned on values of the remainder, which is required for block Gibbs sampling. As an illustrative example, we apply the algorithm in the simplest nontrivial setting of hidden Markov chains. More important, we demonstrate how it applies to Markov random fields on regular lattices and to perfect block Gibbs sampling for binary systems. Copyright Biometrika Trust 2002, Oxford University Press.