Show that this individual transition leaves invariant the conditional distribution xi ∼ Normal (µ, σ2)
A single iteration of Adler's overrelaxation, like one of Gibbs sampling, updates each variable in turn as indicated in equation (30.8). The transition matrix T(x'; x) defined by a complete update of all variables in some fixed order does not satisfy detailed balance. Each individual transition for one coordinate just described does satisfy detailed balance - so the overall chain gives a valid sampling strategy which converges to the target density P(x) - but when we form a chain by applying the individual transitions in a fixed sequence, the overall chain is not reversible. This temporal asymmetry is the key to why overrelaxation can be beneficial. If, say, two variables are positively correlated, then they will (on a short timescale) evolve in a directed manner instead of by random walk, as shown in figure 30.3. This may significantly reduce the time required to obtain independent samples.