If we wish to estimate efficiently the expectation of an arbitrary
function on the basis of the output of a Gibbs sampler, which is better:
deterministic or random sweep? In each case we calculate the asymptotic
variance of the empirical estimator, the average of the function over the
output, and determine the minimal asymptotic variance for estimators that use
no information about the underlying distribution. The empirical estimator has
noticeably smaller variance for deterministic sweep. The variance bound for
random sweep is in general smaller than for deterministic sweep, but the two
are equal if the target distribution is continuous. If the components of the
target distribution are not strongly dependent, the empirical estimator is
close to efficient under deterministic sweep, and its asymptotic variance
approximately doubles under random sweep.