Random-Walk Metropolis and Proposal Scale

Random-Walk Metropolis Updates

A random-walk Metropolis update proposes a move relative to the chain’s current state. The proposal is symmetric: the chance of proposing a displacement in one direction matches the chance of proposing its reverse. The Metropolis acceptance rule then uses the target distribution to decide whether to move. Proposal scale matters because larger attempted moves can cover more distance, but can also land in regions with much lower target probability.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\geq 0}\) be a discrete-time Markov chain with state space \(S\), which may be finite or countable. Write \(\mathcal{F}_n\) for the information available through step \(n\). Let \(\pi\) be a target probability mass function on \(S\), with \(\pi(x)>0\) for every state under consideration. A proposal kernel \(q(x,y)\) gives the probability of proposing \(y\) when the current state is \(x\); for each \(x\), its entries must be nonnegative and sum to one.

Definition: A random-walk proposal has the form \(Y=x+Z\) when the current state is \(x\), where the displacement \(Z\) has a distribution symmetric about zero. On a discrete state space, this means that the proposal probabilities for opposite displacements agree. The Metropolis acceptance probability for a symmetric proposal is \(\alpha(x,y)=\min\{1,\pi(y)/\pi(x)\}\). The chain moves to \(y\) with probability \(q(x,y)\alpha(x,y)\); otherwise it remains at \(x\).

This formula assumes the proposal is symmetric, so \(q(x,y)=q(y,x)\) for distinct states. For an asymmetric proposal the proposal probabilities do not cancel; the Metropolis–Hastings rule from the earlier material on asymmetric proposals includes their ratio. If a proposal produces the current state itself, that is a stay and does not change the chain. In the examples below, the proposal is defined for every state and every possible displacement.

Why the Symmetric Update Preserves the Target

Theorem: Suppose \(S\) is finite or countable, \(\pi\) is a probability mass function with \(\pi(x)>0\), and \(q\) is a probability proposal kernel satisfying \(q(x,y)=q(y,x)\) for all distinct \(x,y\). The transition kernel \(P\) defined by the symmetric Metropolis rule has \(\pi\) as a stationary distribution: \(\pi P=\pi\).

Proof. For distinct states \(x\) and \(y\), the probability flow from \(x\) to \(y\) under \(\pi\) is \(\pi(x)P(x,y)=\pi(x)q(x,y)\min\{1,\pi(y)/\pi(x)\}=q(x,y)\min\{\pi(x),\pi(y)\}\). Because \(q(x,y)=q(y,x)\), this equals \(\pi(y)P(y,x)\). Thus detailed balance holds for every distinct pair. It holds for \(x=y\) as well, since the two sides are identical. For a fixed \(y\), sum these equalities over \(x\). The sum is valid for a finite or countable state space because all terms are nonnegative. The result is \(\sum_x\pi(x)P(x,y)=\sum_x\pi(y)P(y,x)=\pi(y)\sum_xP(y,x)=\pi(y)\), where the last equality uses the fact that row \(y\) of a transition kernel sums to one. Hence \(\pi P=\pi\). \(\square\)

The rule does define a transition kernel. For each current state, proposed moves to other states have probabilities \(q(x,y)\alpha(x,y)\); the remaining probability is assigned to staying at \(x\). Each off-diagonal probability is nonnegative and no greater than \(q(x,y)\), so their sum is at most one. The leftover stay probability is therefore nonnegative, and the entire row sums to one. This check is important when constructing a proposal on a restricted state space.

A Finite Target for Comparing Scales

We will use \(S=\{-2,-1,0,1,2\}\) and target probabilities proportional to \(1,2,4,2,1\), in that state order. Their sum is \(1+2+4+2+1=10\), so \(\pi=(1/10,2/10,4/10,2/10,1/10)\). The entries are positive and sum to one. For an integer scale \(h\), draw a displacement uniformly from \(\{-h,-h+1,\ldots,h\}\). If the proposed destination lies outside \(S\), treat it as a proposal to stay at the current state. This rule applies at every state, not just at the endpoints of \(S\).

Worked Example: Scale One

Take \(h=1\), so each of \(-1,0,1\) is proposed with probability \(1/3\). The rule for out-of-state destinations makes every proposal row well-defined. With rows and columns ordered as \(-2,-1,0,1,2\), the proposal matrix is

Q_1= \begin{bmatrix} \tfrac23&\tfrac13&0&0&0\\ \tfrac13&\tfrac13&\tfrac13&0&0\\ 0&\tfrac13&\tfrac13&\tfrac13&0\\ 0&0&\tfrac13&\tfrac13&\tfrac13\\ 0&0&0&\tfrac13&\tfrac23 \end{bmatrix}.

Each row sums to one: the first and last sum to \(2/3+1/3=1\), and each of the three interior rows sums to \(1/3+1/3+1/3=1\). The off-diagonal proposal probabilities are symmetric. For the Metropolis update, a move from weight \(a\) to weight \(b\) is accepted with probability \(\min\{1,b/a\}\). Thus a move from \(0\) to either neighbour is accepted with probability \(2/4=1/2\); a move from \(-1\) to \(-2\) is accepted with probability \(1/2\); and a move toward a state with larger weight is accepted with probability one.

Applying those probabilities gives the Metropolis transition matrix

P_1= \begin{bmatrix} \tfrac23&\tfrac13&0&0&0\\ \tfrac16&\tfrac12&\tfrac13&0&0\\ 0&\tfrac16&\tfrac23&\tfrac16&0\\ 0&0&\tfrac13&\tfrac12&\tfrac16\\ 0&0&0&\tfrac13&\tfrac23 \end{bmatrix}.

For example, from \(-1\), the proposal to \(-2\) has probability \(1/3\) and acceptance probability \(1/2\), giving transition probability \(1/6\). The proposal to \(0\) is accepted with probability one, giving \(1/3\). The remaining probability is a stay: \(1-1/6-1/3=1/2\). The row sums of \(P_1\) are \(1\), \(1/6+1/2+1/3=1\), \(1/6+2/3+1/6=1\), \(1/3+1/2+1/6=1\), and \(1\), respectively.

Worked Example: Scale Three

Now take \(h=3\), with each displacement in \(\{-3,-2,-1,0,1,2,3\}\) proposed with probability \(1/7\). For example, from \(-2\), displacements \(-3,-2,-1\) all lead outside \(S\), so each becomes a stay. The other possible destinations are \(-1,0,1\). The full proposal matrix is

Q_3= \begin{bmatrix} \tfrac47&\tfrac17&\tfrac17&\tfrac17&0\\ \tfrac17&\tfrac37&\tfrac17&\tfrac17&\tfrac17\\ \tfrac17&\tfrac17&\tfrac37&\tfrac17&\tfrac17\\ \tfrac17&\tfrac17&\tfrac17&\tfrac37&\tfrac17\\ 0&\tfrac17&\tfrac17&\tfrac17&\tfrac47 \end{bmatrix}.

The first and last rows sum to \(4/7+1/7+1/7+1/7=1\); each other row sums to \(3/7+1/7+1/7+1/7+1/7=1\). The matrix is symmetric, including its off-diagonal entries. From \(0\), the proposal to either \(\pm1\) is accepted with probability \(2/4=1/2\), while the proposal to either \(\pm2\) is accepted with probability \(1/4\). From \(-2\), all proposed moves to states in \(S\) go to states of greater target probability and are accepted.

Including rejected proposals in the stay probability gives

P_3= \begin{bmatrix} \tfrac47&\tfrac17&\tfrac17&\tfrac17&0\\ \tfrac1{14}&\tfrac47&\tfrac17&\tfrac17&\tfrac1{14}\\ \tfrac1{28}&\tfrac1{14}&\tfrac{11}{14}&\tfrac1{14}&\tfrac1{28}\\ \tfrac1{14}&\tfrac17&\tfrac17&\tfrac47&\tfrac1{14}\\ 0&\tfrac17&\tfrac17&\tfrac17&\tfrac47 \end{bmatrix}.

At \(0\), for instance, the accepted probabilities to \(\pm1\) are each \((1/7)(1/2)=1/14\), and those to \(\pm2\) are each \((1/7)(1/4)=1/28\). Their sum is \(2/14+2/28=3/14\), so the stay probability is \(1-3/14=11/14\). The centre row sums to \(1\). The row for \(-1\) sums to \(1/14+4/7+1/7+1/7+1/14=1\); the row for \(1\) has the same sum. The endpoint rows each sum to \(4/7+1/7+1/7+1/7=1\).

As a direct stationarity check, the flow from \(0\) to \(2\) is \(\pi(0)P_3(0,2)=(4/10)(1/28)=1/70\). The reverse flow is \(\pi(2)P_3(2,0)=(1/10)(1/7)=1/70\). The theorem gives this equality for every pair, and hence \(\pi P_3=\pi\). It also gives \(\pi P_1=\pi\), since the proposal in the scale-one example is symmetric too.

Acceptance and Movement Are Different

A proposal’s acceptance probability is not itself a measure of how far the chain travels. Staying put may occur because the proposal was already a stay, or because a proposed move was rejected. It is useful to distinguish these cases when examining a trace.

Worked Example: Comparing Movement from the Centre

Start at \(0\). With scale one, the proposal stays at \(0\) with probability \(1/3\), and proposes each neighbour with probability \(1/3\). Each neighbour proposal is accepted with probability \(1/2\). Thus the probability of accepting the proposal, counting an unchanged proposal as accepted, is \(1/3+2(1/3)(1/2)=2/3\). The expected absolute distance moved in one update is \(2(1/3)(1/2)(1)=1/3\).

With scale three, the proposal stays at \(0\) with probability \(3/7\), proposes each of \(\pm1\) with probability \(1/7\), and each of \(\pm2\) with probability \(1/7\). The other two displacement choices lead outside \(S\) and also become stays. The probability of accepting the proposal is therefore \(3/7+2(1/7)(1/2)+2(1/7)(1/4)=9/14\). The expected absolute distance moved is \(2(1/7)(1/2)(1)+2(1/7)(1/4)(2)=2/7\). Comparing \(2/7\) with \(1/3\), the scale-three proposal has a lower acceptance probability and, at this particular state in this particular example, a lower expected movement per update.

These calculations do not establish a universal ranking of scales. The result depends on the target, the state, the proposal rule, and how movement is measured. A larger scale can offer more distant destinations, but the acceptance rule may reject many of them. Conversely, a small scale may be accepted often while taking only short steps.

Reading Short Traces

Worked Example: Two Illustrative Traces

Use the same target and proposal rules, starting from \(0\). For scale one, consider proposals \(+1,+1,-1,-1\). On each of the first two moves the target probability ratio is \(2/4=1/2\); uniforms in the interval \((0,1/2)\) accept these proposals. The third and fourth moves go to higher-weight states, so their acceptance probability is one. The resulting trace is \(0,1,2,1,0\). The particular uniform values are only illustrative; the stated intervals have positive probability under a uniform draw.

For scale three, consider proposals \(+2,-2\) from \(0\). Each is proposed with probability \(1/7\), and each has acceptance probability \(1/4\). A uniform value in \((1/4,1)\), such as \(1/2\), rejects either move. The trace is then \(0,0,0\), with both proposals rejected. This short trace illustrates how a relatively large proposed move can fail to produce movement when the target weight drops sharply. It does not imply that every trace at scale three will be constant.

Both transition matrices preserve the same target, but that fact alone does not say how quickly a chain explores its state space or how useful a finite trace will be. Those questions require more than checking invariance. In practice, scale is assessed by looking at both attempted distances and rejection behaviour, rather than trying to maximize acceptance in isolation.

Common pitfall. Reversing the target ratio gives a wrong acceptance probability. From \(0\) to \(2\), the target probabilities are \(\pi(0)=4/10\) and \(\pi(2)=1/10\). The correct ratio is \(\pi(2)/\pi(0)=(1/10)/(4/10)=1/4\), so the move is accepted with probability \(1/4\). Using \(\pi(0)/\pi(2)=4\) and treating that as an acceptance probability is invalid: probabilities cannot exceed one, and the move to the lower-weight state should not be accepted automatically.

Check Your Understanding

Use the target and proposal conventions in the examples unless a question states otherwise.

For scale one, calculate the acceptance probability for a proposed move from \(-1\) to \(-2\). What is the resulting transition probability?
From \(0\) with scale three, calculate the probability of proposing \(2\), the acceptance probability, and the transition probability to \(2\).
Why must proposals outside \(S\) be assigned a destination before checking whether the proposal rows sum to one?
Give one reason a larger proposal scale might result in less movement over a short trace.
State the symmetry condition that lets the proposal probabilities cancel in the Metropolis acceptance formula. What changes if that condition fails?