Scan Schedules and Component Update Order

Why the Scan Schedule Matters

A Gibbs sampler updates one component of a configuration at a time, drawing that component from its conditional distribution given the others. The schedule determines how those component updates form a transition kernel. In a systematic scan, the components are updated in a fixed order; in a random scan, one component is selected at random at each step. Both schedules can preserve the same target distribution, but they need not have the same transition probabilities or convergence behavior.

Let \(S=S_1\times\cdots\times S_d\) be a finite product state space, and let \(\pi(x)>0\) for every \(x\in S\), with \(\sum_{x\in S}\pi(x)=1\). For component \(\ell\), write \(x_{-\ell}\) for all coordinates except coordinate \(\ell\). The conditional distribution used to update component \(\ell\) is \(\pi_\ell(a\mid x_{-\ell})=\pi(x_{-\ell},a)/\sum_{b\in S_\ell}\pi(x_{-\ell},b)\). Positivity ensures that every denominator is nonzero. Consider a discrete-time chain \((X_n)_{n\ge0}\) on \(S\), on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Its transition matrices use row vectors for distributions.

Kernel products here follow row-vector convention: if the current distribution is \(\mu\), then after a component-\(\ell\) update it is \(\mu K_\ell\). Thus, in the displayed systematic order, the first update is applied first and the distribution after a complete sweep is \(\mu K_{\sigma(1)}\cdots K_{\sigma(d)}\). The chain observed at sweep boundaries is homogeneous in discrete sweep time. A random-scan chain instead takes one randomly selected component update per discrete-time step.

Why Both Schedules Preserve the Target

Proof. Fix a component \(\ell\). For any configuration \(y\), a transition to \(y\) under \(K_\ell\) is possible only from configurations \(x\) with \(x_{-\ell}=y_{-\ell}\). Therefore \(\sum_{x\in S}\pi(x)K_\ell(x,y)=\sum_{a\in S_\ell}\pi(y_{-\ell},a)\pi_\ell(y_\ell\mid y_{-\ell})\). By the definition of the conditional probability, the sum over \(a\) is \(\pi(y_{-\ell})=\sum_{a\in S_\ell}\pi(y_{-\ell},a)\), so the expression is \(\pi(y_{-\ell})\pi_\ell(y_\ell\mid y_{-\ell})=\pi(y)\). This proves \(\pi K_\ell=\pi\) at every \(y\). For a systematic sweep, repeated multiplication gives \(\pi K_{\sigma(1)}\cdots K_{\sigma(d)}=\pi\), since each factor preserves \(\pi\). For random scan, linearity gives \(\pi\sum_\ell w_\ell K_\ell=\sum_\ell w_\ell\pi K_\ell=\sum_\ell w_\ell\pi=\pi\). The weights sum to one, so the mixture is a transition kernel and the stated equality proves invariance. \(\square\)

The result concerns invariance: if a chain starts with distribution \(\pi\), it has distribution \(\pi\) after the update being considered. It does not say that chains started elsewhere approach \(\pi\) at the same rate, or even that different schedules have the same transition matrix. The following calculations make that distinction explicit.

Invariance Is Not a Mixing Comparison

For a sharper comparison, write the two component values as \(x,y\in\{-1,+1\}\). Under this target, the conditional mean of either updated component, given the other, is \(r\) times the other component, where \(r=1/2\): for example, \(\mathbb{E}[X\mid Y=y]=(3/4)y+(1/4)(-y)=y/2\). In random scan, a step updates \(X\) with probability \(1/2\) and otherwise leaves \(X\) unchanged. Therefore \(\mathbb{E}[X_{n+1}\mid X_n=x,Y_n=y]=(x+ry)/2\). The corresponding conditional mean for \(Y\) is \((y+rx)/2\). If the chain starts at \(++\), symmetry gives equal means at each step, and each mean is multiplied by \((1+r)/2=3/4\). Thus after \(n\) random-scan updates, both component means are \((3/4)^n\).

For systematic scan, one complete sweep first gives \(\mathbb{E}[X_{\mathrm{new}}\mid X=x,Y=y]=ry\), then gives \(\mathbb{E}[Y_{\mathrm{new}}\mid X_{\mathrm{new}}]=rX_{\mathrm{new}}\). Starting at \(++\), after \(n\ge1\) complete sweeps the means are \(\mathbb{E}[Y_n]=(1/4)^n\) and \(\mathbb{E}[X_n]=(1/2)(1/4)^{n-1}\). These formulas follow by repeatedly applying the two conditional-mean equations; for example, \(\mathbb{E}[Y_n]=r\mathbb{E}[X_n]=r^2\mathbb{E}[Y_{n-1}]\), with \(\mathbb{E}[Y_0]=1\). The schedules therefore contract these particular discrepancies at different rates. This is not a general claim that systematic scan is always faster: the comparison depends on the target, update order, and how computational effort is counted.

A Common Scan-Schedule Error

A tempting but incorrect calculation is to represent an \(X\)-then-\(Y\) systematic sweep by the average \((K_X+K_Y)/2\). Averaging means that one of the two updates is selected for a single step; it is the random-scan rule, not the fixed-order rule. For the correlated binary target, starting at \(++\), the probability of ending at \(++\) after a systematic sweep is \((3/4)(3/4)=9/16\): \(X\) must first remain \(+\), then \(Y\) must remain \(+\). The random-scan probability of \(++\) in one step from \(++\) is \((1/2)(3/4)+(1/2)(3/4)=3/4\). Confusing the two gives \(3/4\) where the systematic entry is \(9/16\). The correction is to compose the update kernels in order for a sweep, and to average them only when the algorithm actually chooses one component at random per step.

Scan choice matters because it changes what counts as a step, which configurations can be reached in that step, and how dependence between components is removed. In practice, compare schedules at a stated computational cost—for example, one component update versus one full sweep—and examine the transition behavior relevant to the target. The invariant distribution is essential for correctness, but it is not by itself a measure of mixing.