Random-walk Metropolis algorithm

Random-walk Metropolis proposes a symmetric increment from the current state and accepts a proposal

y

from

x

with probability

min {1, π (y) / π (x)}

Table of contents

Poisson Metropolis chain ( $u_{n} = \frac{1}{2} min (1, λ / (n + 1)), d_{n} = \frac{1}{2} min (1, n / λ)$ )

 0  0

A Poisson Metropolis chain samples a Poisson distribution by proposing an upward or downward unit step with equal probability and reflecting a downward proposal at zero into a self-proposal. Its upward and downward transition probabilities are the displayed

u_{n}, d_{n}

, with

d_{0} = 0

, and the diagonal entry is

1 - u_{n} - d_{n}

. For

π_{n} = e^{- λ} λ^{n} / n!

, adjacent stationary fluxes equal

\frac{1}{2} min (π_{n}, π_{n + 1})

. Hence detailed balance holds. Positive adjacent probabilities imply an irreducible Markov chain;

P (0, 0) \geq 1/2

implies aperiodicity. The normalized invariant Poisson distribution implies positive recurrence, so the countable-state Markov chain convergence theorem applies. The boundary proposal probability is essential: forcing every proposal at zero to go upward would require a different acceptance ratio.

Positive-parameter random walk with boundary rejection ( $v^{'} = v + η, η \sim N (0, s^{2})$ )

 0  0

To update a positive parameter, a symmetric additive proposal distribution can be generated on the whole real line. Reject nonpositive proposals; accept positive ones using the target density ratio. The off-diagonal proposal remains symmetric. Repeatedly redrawing until the proposal is positive instead truncates and renormalizes the proposal differently at different current states, so a Hastings correction is then required. A symmetric walk in

lo g v

is another valid method, but its transformed target includes the Jacobian determinant factor

v

Proposal scale and random-walk Metropolis efficiency

 0  0

A small proposal scale increases acceptance while making successive states almost equal. A large scale often proposes low-density states and creates long rejection runs. A pilot comparison can optimize effective sample size of a Markov chain per unit computing time, or expected accepted squared displacement, rather than acceptance alone. Tune on representative functions and then fix the scale for production; an arbitrarily history-dependent adaptation is not automatically a chain with the desired invariant distribution.