Information bounds for Gibbs samplers

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: determinis tic or random sweep? In each case we calculate the asymptotic variance of t he empirical estimator, the average of the function over the output, and de termine the minimal asymptotic variance for estimators that use no informat ion about the underlying distribution. The empirical estimator has noticeab ly smaller variance for deterministic sweep. The variance bound for random sweep is in general smaller than for deterministic sweep, but the two are e qual if the target distribution is continuous. If the components of the tar get distribution are not strongly dependent, the empirical estimator is clo se to efficient under deterministic sweep, and its asymptotic variance appr oximately doubles under random sweep.