This paper studies several different plans for selecting coordinates
for updating via Gibbs sampling. It exploits the inherent features of the Gibbs
sampling formulation, most notably its neighborhood structure, to characterize
and compare the plans with regard to convergence to equilibrium and variance of
the sample mean. Some of the plans rely completely or almost completely on
random coordinate selection. Others use completely or almost completely
deterministic coordinate selection rules. We show that neighborhood structure
induces idempotency for the individual coordinate transition matrices and
commutativity among subsets of these matrices. These properties lead to bounds
on eigenvalues for the Gibbs sampling transition matrices corresponding to
several of the plans. For a frequently encountered neighborhood structure, we
give necessary and sufficient conditions for a commonly employed deterministic
coordinate selection plan to induce faster convergence to equilibrium than the
random coordinate selection plans. When these conditions hold, we also show
that this deterministic selection rule achieves the same worst-case bound on
the variance of the sample mean as that arising from the random selection rules
when the number of coordinates grows without bound. This last result encourages
the belief that faster convergence for the deterministic selection rule may
also imply a variance of the sample mean no larger than that arising for random
selection rules.