Acceptance Diagnostics and Proposal Tuning

What Proposal Tuning Is Trying to Improve

A random-walk Metropolis sampler proposes nearby states and accepts or rejects each proposal according to the target distribution. If proposals are too conservative, the chain may move only a little at each iteration. If they are too aggressive, many proposals may be rejected. Acceptance rate is therefore useful, but it does not measure how much the chain moves when it does accept, nor how quickly it explores the particular features we want to estimate.

Let \((X_n)_{n\ge0}\) be a Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Suppose the target assigns positive probability \(\pi(x)\) to each \(x\in S\), with \(\sum_{x\in S}\pi(x)=1\). A proposal kernel \(R(x,y)\) gives the probability of proposing \(y\) from \(x\). For \(y\ne x\), the Metropolis-Hastings acceptance probability is

\alpha(x,y)=\min\left\{1,\frac{\pi(y)R(y,x)}{\pi(x)R(x,y)}\right\},

when \(R(x,y)>0\); proposals with \(R(x,y)=0\) cannot occur and need no acceptance probability. A rejected proposal leaves the chain at \(x\). For a symmetric random-walk proposal, \(R(x,y)=R(y,x)\), so \(\alpha(x,y)=\min\{1,\pi(y)/\pi(x)\}\). In continuous state spaces the same formula uses target and proposal densities in place of probability masses.

Definition: Over \(N\) iterations, the empirical acceptance rate is the number of accepted proposals divided by \(N\). For a numerical state, the mean squared jump distance is \(N^{-1}\sum_{n=0}^{N-1}(X_{n+1}-X_n)^2\); rejected proposals contribute zero. One may also report the mean squared distance conditional on acceptance, which describes accepted moves only. These are different diagnostics.

For an observable \(h:S\to\mathbb{R}\), effective sample size (ESS) summarizes the effect of serial dependence on estimating its mean. When the chain is stationary and the autocorrelations are summable, define \(\rho_k=\operatorname{Corr}(h(X_0),h(X_k))\) and \(\tau_h=1+2\sum_{k\ge1}\rho_k\). The asymptotic ESS per \(N\) iterations is \(N/\tau_h\). It depends on \(h\): a proposal can be effective for one feature of the target and less effective for another. In practice, autocorrelations and ESS must be estimated from a finite run, so they are diagnostics rather than exact guarantees.

Why the Metropolis Rule Preserves the Target

Proposition: If \(S\) is finite, \(\pi(x)>0\) for every \(x\), and the proposal is symmetric, the Metropolis transition kernel \(K\) satisfies detailed balance: \(\pi(x)K(x,y)=\pi(y)K(y,x)\) for all \(x,y\). Consequently \(\pi\) is stationary for \(K\).

Proof. For distinct \(x,y\) with \(R(x,y)=R(y,x)>0\), the off-diagonal transition probability is \(K(x,y)=R(x,y)\alpha(x,y)\). Thus \(\pi(x)K(x,y)=R(x,y)\min\{\pi(x),\pi(y)\}\), which is unchanged when \(x\) and \(y\) are exchanged. If \(R(x,y)=0\), symmetry gives \(R(y,x)=0\), so both off-diagonal flows are zero. For \(x=y\), detailed balance is the identity \(\pi(x)K(x,x)=\pi(x)K(x,x)\). Summing detailed balance over \(x\), for fixed \(y\), gives \(\sum_x\pi(x)K(x,y)=\pi(y)\sum_xK(y,x)=\pi(y)\), because row \(y\) of \(K\) sums to one. This is \(\pi K=\pi\), so \(\pi\) is stationary. \(\square\)

There is a useful way to check the flow calculation: for an unordered pair \(\{x,y\}\) with symmetric proposal probability \(R(x,y)\), the accepted stationary flow from \(x\) to \(y\) is \(R(x,y)\min\{\pi(x),\pi(y)\}\), and the flow from \(y\) to \(x\) has that same value. The total across both directions is therefore \(2R(x,y)\min\{\pi(x),\pi(y)\}\), not just one copy.

Two Proposal Scales on One Target

Worked Example: Acceptance and Jump Distance

Take \(S=\{-1,0,1\}\) and target probabilities \(\pi(-1)=\tfrac14\), \(\pi(0)=\tfrac12\), \(\pi(1)=\tfrac14\). Compare two symmetric random-walk proposals. Scale 1 proposes an increment of \(+1\) or \(-1\), each with probability \(\tfrac12\). Scale 2 proposes one of \(+1,-1,+2,-2\), each with probability \(\tfrac14\). Any proposal outside \(S\) is rejected. The target probabilities sum to \(\tfrac14+\tfrac12+\tfrac14=1\).

For scale 1, from either endpoint the inward proposal is accepted with probability \(1\), since the target probability increases, and the outward proposal is invalid. From 0, each proposal to an endpoint has acceptance probability \((\tfrac14)/(\tfrac12)=\tfrac12\). Including rejected proposals as stays, the transition matrix, in state order \((-1,0,1)\), is

K_1= \begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac14&\tfrac12&\tfrac14\\ 0&\tfrac12&\tfrac12 \end{bmatrix}.

Each row sums to one: \(\tfrac12+\tfrac12=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(\tfrac12+\tfrac12=1\). The stationary check gives \(\pi K_1=(\tfrac14,\tfrac12,\tfrac14)\): its three entries are \(\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac14=\tfrac14\), \(\tfrac14\cdot\tfrac12+\tfrac12\cdot\tfrac12+\tfrac14\cdot\tfrac12=\tfrac12\), and \(\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac12=\tfrac14\). The acceptance probability is \(\tfrac12\) at each state, so the stationary mean acceptance rate is \(\tfrac12\). The mean squared jump distance is \(\tfrac14(\tfrac12\cdot1)+\tfrac12(\tfrac12\cdot1)+\tfrac14(\tfrac12\cdot1)=\tfrac12\); here each nonzero jump has squared size 1.

For scale 2, from \(-1\), the proposal to 0 is accepted with probability 1 and the proposal to 1 is accepted with probability \(\tfrac12\); the other two proposals are outside \(S\). From 0, each proposal to an endpoint is accepted with probability \(\tfrac12\), and the two proposals outside \(S\) are rejected. By symmetry the row for 1 mirrors the row for \(-1\). Thus

K_2= \begin{bmatrix} \tfrac58&\tfrac14&\tfrac18\\ \tfrac18&\tfrac34&\tfrac18\\ \tfrac18&\tfrac14&\tfrac58 \end{bmatrix}.

Every row sums to one: \(\tfrac58+\tfrac14+\tfrac18=1\), \(\tfrac18+\tfrac34+\tfrac18=1\), and \(\tfrac18+\tfrac14+\tfrac58=1\). Multiplying by \(\pi\), the first entry is \(\tfrac14\cdot\tfrac58+\tfrac12\cdot\tfrac18+\tfrac14\cdot\tfrac18=\tfrac14\); the middle entry is \(\tfrac14\cdot\tfrac14+\tfrac12\cdot\tfrac34+\tfrac14\cdot\tfrac14=\tfrac12\); and the last is \(\tfrac14\). Hence \(\pi K_2=\pi\).

At either endpoint the acceptance probability is \(\tfrac14\cdot1+\tfrac14\cdot\tfrac12=\tfrac38\). At 0 it is \(\tfrac14\cdot\tfrac12+\tfrac14\cdot\tfrac12=\tfrac14\). Averaging over the target gives \(\tfrac14\cdot\tfrac38+\tfrac12\cdot\tfrac14+\tfrac14\cdot\tfrac38=\tfrac5{16}\). At an endpoint the mean squared jump per iteration is \(\tfrac14\cdot1^2+\tfrac14\cdot\tfrac12\cdot2^2=\tfrac34\); at 0 it is \(\tfrac14\cdot\tfrac12\cdot1^2+\tfrac14\cdot\tfrac12\cdot1^2=\tfrac14\). The stationary mean squared jump is therefore \(\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac14=\tfrac12\). Conditional on acceptance, the mean squared jump is \((\tfrac12)/(\tfrac5{16})=\tfrac85\), compared with \((\tfrac12)/(\tfrac12)=1\) for scale 1.

Check: scale 2 has lower acceptance, \(\tfrac5{16}<\tfrac12\), but the same unconditional mean squared jump, \(\tfrac12\). Its accepted moves are larger on average, but it accepts less often. Neither acceptance rate nor accepted jump size alone captures the whole comparison.

Effective Sample Size Depends on the Quantity

Result: Suppose a finite Markov chain is stationary, \(h\) has positive finite variance, and \(K h=\lambda h\) for a centered function \(h\), with \(|\lambda|<1\). Then \(\rho_k=\lambda^k\) and \(\tau_h=(1+\lambda)/(1-\lambda)\).

Proof. The Markov property gives \(\mathbb{E}[h(X_k)\mid X_0]=(K^kh)(X_0)=\lambda^k h(X_0)\), by applying \(Kh=\lambda h\) repeatedly. Multiplying by \(h(X_0)\) and taking expectations gives \(\operatorname{Cov}(h(X_0),h(X_k))=\lambda^k\operatorname{Var}(h(X_0))\), since \(h\) is centered. Dividing by the positive variance gives \(\rho_k=\lambda^k\). Because \(|\lambda|<1\), the geometric series converges, and \(\tau_h=1+2\sum_{k\ge1}\lambda^k=1+2\lambda/(1-\lambda)=(1+\lambda)/(1-\lambda)\). \(\square\)

Worked Example: ESS for the Center-State Indicator

Use \(h(x)=\mathbf{1}_{\{0\}}(x)-\tfrac12\), the centered indicator of being at 0. Under \(\pi\), its mean is 0 and its variance is \(\tfrac12(\tfrac12)^2+\tfrac12(-\tfrac12)^2=\tfrac14\). For scale 1, multiplying \(K_1\) by the column vector \((-\tfrac12,\tfrac12,-\tfrac12)\) gives \((0,0,0)\). Thus \(K_1h=0\), so every positive-lag covariance is zero; \(\tau_h=1\), and the asymptotic ESS is \(N\).

For scale 2, multiplication by \(K_2\) gives \((-\tfrac14,\tfrac14,-\tfrac14)=\tfrac12 h\). The result just proved applies with \(\lambda=\tfrac12\), giving \(\rho_k=(\tfrac12)^k\) and \(\tau_h=(1+\tfrac12)/(1-\tfrac12)=3\). Its asymptotic ESS is \(N/3\). The calculation is checked directly at lag 1: \(\operatorname{Cov}(h(X_0),h(X_1))=\tfrac12\operatorname{Var}(h(X_0))=\tfrac18\), so \(\rho_1=(\tfrac18)/(\tfrac14)=\tfrac12\).

Worked Example: The Same Acceptance Rates, a Different Comparison

Now take \(h(x)=x\). Its stationary mean is \(-\tfrac14+0+\tfrac14=0\), and its variance is \(\tfrac14\cdot1+\tfrac12\cdot0+\tfrac14\cdot1=\tfrac12\). For scale 1, \(K_1h=(-\tfrac12,0,\tfrac12)=\tfrac12h\). For scale 2, \(K_2h=(-\tfrac12,0,\tfrac12)=\tfrac12h\) as well: at \(-1\), the calculation is \(-\tfrac58+\tfrac18=-\tfrac12\); at 0 it is \(-\tfrac18+\tfrac18=0\); at 1 it is \(-\tfrac18+\tfrac58=\tfrac12\).

Consequently both scales have \(\rho_k=(\tfrac12)^k\), \(\tau_h=3\), and asymptotic ESS \(N/3\) for estimating the mean of \(x\), even though their acceptance rates are \(\tfrac12\) and \(\tfrac5{16}\). This example and the center-indicator calculation show why a proposal comparison should specify the quantity being estimated: relative efficiency can depend on that quantity.

Practical Interpretation and Common Pitfalls

Acceptance rate is a useful warning signal, not a universal optimization objective. A high rate can accompany small moves; a low rate can accompany occasional long accepted moves. Whether those moves improve estimation depends on the target, the proposal, and the observable. The finite-state calculations above establish this point without relying on a particular recommended acceptance percentage. Rules of thumb derived for one asymptotic setting should not be treated as universal prescriptions for other dimensions, targets, or samplers.

Common mistake. It is incorrect to say that scale 2 has mean squared jump \(\tfrac34\) because the endpoint calculation is \(\tfrac34\). That value is conditional on starting at an endpoint, not averaged over the stationary target. The center contributes \(\tfrac14\), and the stationary average is \(\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac14=\tfrac12\). Likewise, the overall acceptance rate is not the endpoint rate \(\tfrac38\): the center has stationary probability \(\tfrac12\) and acceptance rate \(\tfrac14\), giving the overall rate \(\tfrac5{16}\). State-specific quantities must be weighted by the target probabilities before they are reported as stationary diagnostics.

In applications, compare proposals using several complementary quantities: acceptance rate, movement per iteration, and ESS or Monte Carlo standard error for the actual estimands. If the chain is not plausibly sampling its target, an estimated ESS from a finite run may itself be unreliable; these summaries do not replace checks of the sampled trajectories and dependence structure.

Check Your Understanding

Use the definitions and calculations above to check each answer, keeping state-specific and target-averaged quantities distinct.

For scale 2, what is the acceptance probability at state 0, and why is it not the overall stationary acceptance rate?
For scale 1, verify the stationary mean squared jump distance by averaging the endpoint and center contributions.
For an observable satisfying \(Kh=\tfrac13h\), what are \(\rho_k\) and \(\tau_h\), assuming the hypotheses of the eigenfunction result?
Why can two proposal scales have different acceptance rates but the same ESS for a particular observable?
Explain why the mean squared jump conditional on acceptance should not be reported as the mean squared jump per iteration.