Motivation
Independent sampling can be difficult even when a target's relative weights are easy to evaluate. A Markov-chain method instead starts at one state and repeatedly proposes a local change. Its later states can approach the target law, but consecutive outputs are dependent. A correct discussion therefore needs two arguments: why the transition has the desired invariant distribution, and why the chain can actually reach that distribution from its chosen start.
Detailed balance answers only the first question. An algorithm that never moves can satisfy detailed balance for many targets. A chain that alternates between two states can preserve a target law yet fail to converge from a fixed initial state. We will prove additional connectivity and positive-holding conditions, then derive convergence from a positive power of the transition matrix rather than citing an unexplained “mixing” principle.
The entire setting is finite. We give complete Metropolis–Hastings and random-scan Gibbs programs for a four-state target, together with an exact stationary variance calculation. No conclusion is asserted for general countable or continuous state spaces, and no general MCMC central limit theorem is claimed.
Definitions
Let have states and positive target weights , with .
Definition 9.1.1
(Transition matrix, stationarity and detailed balance)
A transition matrix on has nonnegative entries and row sums one. Distributions are row vectors, so one update sends to . A distribution is stationary for if . The matrix satisfies detailed balance with respect to if for every pair of states .
Detailed balance is a pairwise condition, stationarity a condition on whole columns. A second description makes the relation between them exact.
Concept lensAlgebraic
Detailed balance as symmetry of one matrix
Let . The entry of is , the probability that a chain started from is at at time zero and at at time one. Detailed balance says precisely that is symmetric, that is, the pair has the same joint law as . Stationarity says only that the column sums of equal : the th column sum is , while the th row sum is because rows of sum to one. Symmetry makes column sums equal row sums, so detailed balance implies stationarity. The converse fails: the three-state rotation preserves the uniform law, yet has entry at and at .
The Metropolis construction is designed to produce the symmetric form directly.
Definition 9.1.2
(Metropolis–Hastings kernel and its lazy version)
Let be a row-stochastic proposal matrix. When , a proposal from to is accepted with probability ; missing reverse support makes this probability zero. For set times that acceptance probability, and put all remaining mass on . The lazy version is , meaning an additional probability one half of staying without proposing.
Definition 9.1.3
(Mutual-proposal graph, irreducibility and period)
The mutual-proposal graph joins distinct states when both and are positive. A kernel is irreducible if every state can reach every other in finitely many steps with positive probability. The period of a state is the greatest common divisor of its positive-probability return times; a kernel is aperiodic if every state has period one.
Connectivity of the undirected mutual-proposal graph will imply irreducibility, and a positive probability of staying gives return time one and hence period one.
Definition 9.1.4
(Total variation distance)
For distributions on the finite set , the total variation distance is .
It bounds the difference of expectations of a function by its range times that distance. The observable in our program is an indicator, so its range is one.
Theorem/proposition
Theorem 9.1.5
(Metropolis balance and actual finite-state accessibility)
The Metropolis kernel and its lazy version preserve . Their off-diagonal transitions are positive exactly on mutual-proposal edges. If that graph is connected, is irreducible and aperiodic, and with every entry of is positive.
Theorem 9.1.6
(A positive power gives convergence, not merely invariance)
Let preserve and suppose is strictly positive. Put . Row sums imply . If , then for every starting distribution,
Thus is the unique stationary distribution and the law converges to it. If , then , where every row of is uniform; is uniform and for every .
Theorem 9.1.7
(Positive finite-product Gibbs sampling converges)
On a finite product of nonempty coordinate sets, assume every configuration has positive target probability. Choose one coordinate uniformly and replace it by its exact conditional target law given all other coordinates. This random-scan Gibbs kernel satisfies detailed balance, is irreducible and aperiodic, and its th power is strictly positive. The preceding convergence argument therefore applies. Structural zeros require a separate accessibility analysis.
Proof sketch or proof idea
Proof
(Balance, mutual edges and padding by holding)
For distinct states, the Metropolis probability flow equals , symmetric in the two states. Diagonal balance is automatic. Summing the balance equations proves stationarity, and laziness preserves it. Positive target weights make the accepted edges exactly the mutual edges. A connecting path has length at most . Positive diagonal entries pad any shorter path to length , proving positivity of every entry of . Holding probability also proves aperiodicity directly.
Proof
(Splitting off a uniform part of a positive power)
Write for the matrix with every row uniform. Each row of dominates times that uniform row, so, when , write with stochastic. Multiplication by a stochastic matrix cannot increase total variation: expand each output coordinate and apply the triangle inequality. Two input distributions have equal mass, so their difference times is zero. Each block of steps therefore contracts their distance by at least . Apply this to and stationary , and use nonexpansion for leftover steps. A second stationary law would have a distance from that tends to zero while remaining constant, proving uniqueness. When , the row lower bound and row sums one force every entry of to be . Stationarity then forces to be uniform, and all distributions after steps remain .
Proof
(Gibbs balance and a coordinate-by-coordinate path)
For Gibbs, configurations differing only in the selected coordinate have flow equal to the probability of the common remaining coordinates times the product of the two conditional probabilities. That product is symmetric. Summing coordinate kernels preserves balance. From any configuration to another, update coordinates one through to their desired final values. Every conditional choice is positive, including retaining an already correct value. The probability of that specified coordinate sequence and its values is positive, so every entry of the th power is positive. It also permits a self-update, proving aperiodicity.
Proof X-ray
Where each hypothesis enters the convergence proof
Balance proves only that a chain already started at the target keeps that law; every further conclusion needs a separate hypothesis. Positivity of all target weights is used to make the acceptance ratio positive whenever the reverse proposal is positive, so the accepted moves are exactly the mutual edges. The holding probability one half is used twice: it pads every connecting path to the same length , so that a single power is positive in every entry, and it gives aperiodicity. The non-obvious move is the decomposition . Since and both have total mass one, : the uniform part forgets the starting point entirely, and only the remainder, of weight , can carry a difference forward. The argument closes by taking and using ; this is the only place stationarity enters. Without it the same estimate shows that two copies of the chain merge, but not that they merge at . For Gibbs, positivity of every configuration replaces both holding and the mutual-edge condition; with a structural zero the coordinate path can be blocked, as the last worked example shows.
Worked examples
Worked example 9.1.8
(A two-state chain triples the asymptotic standard error)
Let have diagonal entries and off-diagonal entries . Its stationary law is uniform. For the state-one indicator, the centered vector is and is an eigenvector with eigenvalue . Consequently the stationary lag- covariance is . For a stationary average of observations,
For this is approximately , whereas independent indicators would give . As grows, tends to . The asymptotic standard error is three times the independent-sample value. Calling an effective sample-size proxy summarizes this variance ratio; it does not produce that many actual independent observations.
The covariance identity comes from expanding the square of the centered sum: stationarity makes each pair with separation have the same covariance, and there are such pairs in each order. For any finite stationary chain, , where . The positive-power contraction bounds these conditional centered expectations geometrically. Their absolute covariances are therefore summable, yielding a stationary mean-square error of order . This does not prove a normal approximation or justify estimating the constant from one short trajectory.
Worked example 9.1.9
(Complete Metropolis and Gibbs computations on four states)
Encode binary pairs as zero through three, with weights . The probability that the low-order bit (state & 1) is one is . Metropolis proposes flipping either bit with equal probability and uses the extra half-holding step. Gibbs chooses a bit and samples its two possible values from their conditional weights. The code also constructs their exact finite transition matrices and computes the stationary mean-variance formula above.
import math
import random
weights = [1.0, 2.0, 2.0, 5.0]
pi = [w / sum(weights) for w in weights]
values = [0.0, 1.0, 0.0, 1.0]
def mh_step(state, rng):
if rng.random() < 0.5:
return state
proposed = state ^ (1 << rng.randrange(2))
ratio = min(1.0, weights[proposed] / weights[state])
return proposed if rng.random() < ratio else state
def gibbs_step(state, rng):
bit = 1 << rng.randrange(2)
zero, one = state & ~bit, state | bit
chance_one = weights[one] / (weights[zero] + weights[one])
return one if rng.random() < chance_one else zero
def transition(kind):
P = [[0.0] * 4 for _ in range(4)]
for i in range(4):
for bit in [1, 2]:
if kind == "mh":
j = i ^ bit
P[i][j] += 0.25 * min(1.0, weights[j] / weights[i])
else:
zero, one = i & ~bit, i | bit
total = weights[zero] + weights[one]
P[i][zero] += 0.5 * weights[zero] / total
P[i][one] += 0.5 * weights[one] / total
if kind == "mh":
P[i][i] = 1.0 - sum(P[i])
return P
def stationary_mean_variance(P, n):
mean = sum(p * value for p, value in zip(pi, values))
g = [value - mean for value in values]
z = list(g)
total = n * sum(p * x*x for p, x in zip(pi, g))
for lag in range(1, n):
z = [sum(a * b for a, b in zip(row, z)) for row in P]
covariance = sum(p * a * b for p, a, b in zip(pi, g, z))
total += 2 * (n - lag) * covariance
return total / (n * n)
for name, step, seed in [("mh", mh_step, 2026),
("gibbs", gibbs_step, 2027)]:
P = transition(name)
assert all(math.isclose(sum(row), 1.0) for row in P)
assert all(math.isclose(pi[i] * P[i][j], pi[j] * P[j][i])
for i in range(4) for j in range(4))
rng, state = random.Random(seed), 0
for _ in range(500):
state = step(state, rng)
output = []
for _ in range(20000):
state = step(state, rng)
output.append(values[state])
mean = math.fsum(output) / len(output)
descriptive = mean * (1 - mean)
naive_se = math.sqrt(descriptive / len(output))
model_se = math.sqrt(stationary_mean_variance(P, len(output)))
print(name, round(mean, 6), round(naive_se, 6), round(model_se, 6))
Printed columns are the observed mean, an independence-based standard error, and the exact stationary-model reference standard error. The last column is not an interval coverage guarantee for this nonstationary initialized run. The burn count of 500 is illustrative; it does not make the start exactly stationary. The positive-power bound can instead bound initialization bias: for an observable of range , every average after burn steps has mean bias at most .
Each sampler step here uses a constant number of table lookups. General conditional sampling or target evaluation may be expensive. The demonstration stores outputs, so its storage is beyond the finite target; the exact reference variance costs arithmetic. Those costs are distinct from the chain's small evolving state. A real problem rarely permits an exact transition-matrix variance calculation at this scale.
Worked example 9.1.10
(Balance survives two different convergence failures)
A two-state kernel that always flips preserves the uniform target and satisfies balance, but from state zero its laws alternate forever. Adding positive holding repairs this periodicity. For a different failure, let a binary-pair target have mass only on and . Single-coordinate Gibbs cannot move between them without entering a zero-mass configuration. Both states are absorbing, so burn-in never selects the target mixture from a fixed start. A move that changes both coordinates can repair accessibility. Laziness alone cannot connect the classes.
Common mistakes
The first error concerns the hypothesis of the accessibility theorem: connectivity is required of the mutual-proposal graph, not of the proposal itself.
Counterexample mode
An irreducible proposal with a frozen Metropolis kernel
Claim: if the proposal matrix is irreducible, then so is the Metropolis kernel. Take three states and the one-way cycle , which is irreducible. For any positive target, the proposal from to (indices mod 3) is accepted with probability , because . Every proposal is rejected, so and . Started at state , the law stays at the point mass , whose total variation distance from is for every . The repaired hypothesis is connectivity of the mutual-proposal graph; for instance, proposing each of the two other states with probability one half makes every pair mutual, and the theorem then applies.
For nonsymmetric proposals, omitting the proposal ratio from the acceptance probability also changes the invariant law.
Common mistake
(Discarding repeated states)
Repeated states are genuine sampler outputs, including rejected proposals and deliberate holding steps. Discarding them changes the observation rule. For the two-state chain with weights one and three studied in the exercises, every actual state change switches to the other state. Recording only those changes therefore produces an alternating list with limiting proportions one half each, instead of the target proportions one quarter and three quarters. The repeated visits encode different dwell times, which are part of how the target law is represented. Count elapsed chain steps when applying the mean-variance formula; a requested number of accepted moves is a different, state-dependent sampling protocol.
Common mistake
(Treating an initialized or thinned chain as independent)
The stationary covariance formula must not be copied unchanged to an arbitrary initialized chain. Convergence of its one-time distribution addresses initialization, while autocorrelation addresses dependence after stationarity. Thinning or retaining every tenth draw does not prove independence. Empirical autocorrelation estimates and batch means can be useful diagnostics, but a noisy short-trajectory estimate is not a theorem about precision. Here the finite matrix supplies a reference that most large simulations do not have.
No: any fixed distribution can play its role, and that form is the one that reaches infinite state spaces.
A path to generalization
Does the convergence proof need the uniform row?
No: any fixed distribution can play its role, and that form is the one that reaches infinite state spaces.
Suppose every row of dominates for one fixed distribution . Then with stochastic when , and because both laws have mass one, so each block again multiplies the distance by at most . This minorization form makes sense where no uniform law exists, such as countable or continuous spaces; there it usually holds only on part of the space, and the additional arguments are beyond this unit.
Summary
Metropolis balance controls the target law, mutual support controls accessibility, and positive holding controls periodicity. Positive finite Gibbs conditionals give analogous guarantees. A strictly positive transition power proves actual geometric convergence. Dependent-sample error then needs covariance terms; the finite stationary calculation and its initialization qualification make those terms explicit without invoking a general MCMC CLT.
Exercises
Exercise 9.1.11
(Two target weights are one and three. A proposal always switches states, followed by Metropolis acceptance and an extra half-holding step. Find the transition matrix and verify detailed balance.)
Foundation
Solution · Answer
The target is . From the light state the switch is always accepted; from the heavy state it is accepted with probability . The lazy transition matrix is . Forward target flow is , and reverse flow is . Row sums are one; positive off-diagonal and diagonal entries supply accessibility and aperiodicity.
Exercise 9.1.12
(A symmetric two-state chain switches with probability . For its state-one indicator, find the lag- covariance and the limit of times the stationary mean variance. Compare with independent observations.)
Core
Solution · Answer
The centered indicator is an eigenvector with eigenvalue , so . The limit is . Independent indicators would give limit , so asymptotic variance is four times larger and standard error twice as large. This variance calculation does not establish a normal approximation.
Exercise 9.1.13
(For binary configurations with weights , find both Gibbs coordinate conditional probabilities of the value one at . Verify balance for the edge from to under random scan.)
Core
Solution · Answer
The first-coordinate conditional probability of one is ; the second is . Random scan moves from to with probability , and back with probability . Their target masses are and , so both flows are . Full positivity also permits coordinate-by-coordinate paths between every pair.
Exercise 9.1.14
(A positive-power bound has and . Bound the total variation after twelve steps and the mean bias for a function with values in . Give a burn count sufficient to make this bias bound at most .)
Core
Solution · Answer
Twelve steps contain four complete blocks, giving total variation at most and bias at most . To bound bias by , require . Twenty-one blocks suffice, since is about , so is sufficient. These conservative numbers illustrate why merely choosing a familiar burn count is not a quantitative proof.