CMP.9:5.3 - Correct a local walk before using it as a sampler

Sample uniformly from three states connected in a path, 0—1—2. A walk that chooses an adjacent state uniformly spends stationary probabilities (1/4,1/2,1/4): the middle state has twice as many incident choices. Uniform selection among neighbors does not imply uniform selection among visited states.

Correct a proposed move x to y by accepting it with probability

min(1, π(y)*q(x|y)/(π(x)*q(y|x))),

where π is the target and q the proposal probability. A rejection retains x. For positive target weights on connected states, the probability flow on either direction of an edge becomes the same minimum of the two proposed flows, so detailed balance holds. Normalizing constants cancel in the ratio.

For this uniform target, accept an end-to-middle move with probability 1/2 and a middle-to-end move with probability 1. The transition matrix, in state order 0,1,2, is

1/2  1/2   0
1/2   0   1/2
 0   1/2  1/2

Its rows and columns each sum to one, so the uniform law is stationary. The finite chain is connected and has self-transitions, hence converges from any start. Its other eigenvalues are 1/2 and -1/2; for this small matrix, powers give an explicit decreasing transient. For instance, starting at 0 gives (1/2,1/2,0) after one step and (1/2,1/4,1/4) after two, still not uniform.

If the three target weights change to (1,2,1), the original uncorrected neighbor walk has that stationary law. Reusing the former uniform-target acceptance probabilities would now be wrong. In either case, adjacent states are dependent observations; an independent-draw variance formula cannot be justified by the stationary law alone.