The Independence Metropolis Sampler

How an Independence Proposal Works

An independence proposal draws each candidate from the same distribution, regardless of the chain's current state. This makes the proposal easy to sample, but it places a particular burden on its tails: the proposal must be able to reach regions that matter under the target. The ratio of target density to proposal density determines whether a proposed move is accepted and provides a direct way to assess that coverage.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((X_n)_{n\ge0}\) be a discrete-time Markov chain with state space \(S\). Write \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) for its natural filtration. Suppose the target distribution has probability density or probability mass function \(\pi\), and the proposal has density or mass function \(q\), both relative to the same underlying measure. Thus \(\int_S \pi(x)\,dx=1\) in a continuous space, or \(\sum_{x\in S}\pi(x)=1\) in a discrete space, with the corresponding condition for \(q\).

Assume that \(q(x)>0\) whenever \(\pi(x)>0\). This support condition ensures that a state with positive target weight has a defined, finite target-to-proposal ratio. At each step, draw \(Y\) from \(q\), independently of the current state \(X_n=x\). Accept the proposal with probability \(\alpha(x,Y)\); if it is rejected, set \(X_{n+1}=x\). The draws used to implement the proposal and acceptance decision can be included in the probability space.

The rules for zero-target states complete the transition mechanism. A proposal with \(\pi(y)=0\) is rejected when the current state has positive target density. If \(\pi(x)=0\) and \(q(x)>0\), accept a proposal with positive target density with probability \(1\), and reject a proposal with zero target density. Finally, if \(\pi(x)=q(x)=0\), define the transition from \(x\) to draw \(Y\sim q\) and move to \(Y\). This last row is a valid probability distribution; such states have zero target probability. These completions give a transition rule for every state under the stated support condition. In ordinary use the chain is initialized in the positive-target support, and it remains there.

Why This Acceptance Rule Preserves the Target

For a proposed move between two positive-target states, the probability flow from \(x\) to \(y\) before accounting for rejected moves is \(\pi(x)q(y)\alpha(x,y)\). The acceptance rule balances this flow against the reverse flow. This is detailed balance: for distinct states, target mass at \(x\) times transition probability from \(x\) to \(y\) equals target mass at \(y\) times the reverse transition probability.

Proof. First take \(x\ne y\) with \(\pi(x)>0\) and \(\pi(y)>0\). The support condition gives \(q(x)>0\) and \(q(y)>0\). Set \(a=\pi(x)q(y)\) and \(b=\pi(y)q(x)\), both positive. The forward accepted flow is \(a\min(1,b/a)=\min(a,b)\). Reversing \(x\) and \(y\), the accepted flow is \(b\min(1,a/b)=\min(a,b)\). The two flows are equal. If \(\pi(x)>0\) and \(\pi(y)=0\), then the move from \(x\) to \(y\) is rejected, so its flow is zero; the reverse flow is also zero because it is multiplied by \(\pi(y)=0\). Thus detailed balance holds for distinct states, including target-zero states. The diagonal equality holds automatically. Summing detailed balance over \(x\) gives, for each \(y\), \(\sum_x\pi(x)K(x,y)=\pi(y)\sum_xK(y,x)=\pi(y)\), since each row of a transition kernel sums to \(1\). This is \(\pi K=\pi\). \(\square\)

This calculation also explains why the acceptance rule has its particular form. For a pair \(x,y\) with positive target and proposal weights, any acceptance probabilities bounded by \(1\) have accepted forward flow at most \(a\) and accepted reverse flow at most \(b\). A balanced pair of flows therefore cannot exceed \(\min(a,b)\). The rule above attains exactly that flow in both directions. It is the largest pairwise balanced accepted flow available for this proposal.

Worked Finite-State Calculations

Tail Coverage and a Uniform Bound

The weight \(w(x)=\pi(x)/q(x)\) is large where the target puts relatively more mass than the proposal. When this ratio is unbounded, the proposal can undersample some target-tail regions. A chain that reaches such a region may then reject many proposals: candidates from the more typical proposal region have smaller weights and hence small acceptance probabilities.

Proof. At a positive-target current state \(x\), \(w(x)\le M\). For a proposed state \(y\) with positive target density, the accepted-move density is \(q(y)\alpha(x,y)=q(y)\min(1,w(y)/w(x))=\min(q(y),\pi(y)/w(x))\). The bound \(w(y)\le M\) gives \(q(y)=\pi(y)/w(y)\ge\pi(y)/M\), and \(w(x)\le M\) gives \(\pi(y)/w(x)\ge\pi(y)/M\). The minimum of two quantities each at least \(\pi(y)/M\) is at least \(\pi(y)/M\). Integrating this accepted-move density over \(A\) gives an accepted transition probability at least \(\pi(A)/M\). Rejected proposals can only add probability to \(K(x,A)\), not subtract from it, so \(K(x,A)\ge\pi(A)/M\). In a discrete space the same argument is a sum over \(y\in A\) rather than an integral. \(\square\)

In the finite example, the largest weight is \(M=\tfrac32\), so this bound gives \(K(x,A)\ge\tfrac23\pi(A)\) for every positive-target current state. The proposition is useful as a diagnostic: bounded target-to-proposal ratios guarantee that no target region is arbitrarily difficult to reach in one step under this bound. If the ratio is unbounded, this particular uniform guarantee is unavailable.

Common Mistake and Practical Checks

Common mistake: reversing the ratio. In the finite example, the correct acceptance probability from state \(1\) to state \(3\) is \(\min\{1,w(3)/w(1)\}=\min\{1,(\tfrac12)/(\tfrac32)\}=\tfrac13\). Reversing the ratio gives \(\min\{1,w(1)/w(3)\}=\min\{1,3\}=1\), which is wrong. It also breaks detailed balance: with the incorrect rule, the flow from \(1\) to \(3\) would be \(\pi(1)q(3)\cdot1=\tfrac12\cdot\tfrac13=\tfrac16\). The reverse acceptance would be \(\tfrac13\), giving reverse flow \(\pi(3)q(1)\cdot\tfrac13=\tfrac16\cdot\tfrac13\cdot\tfrac13=\tfrac1{54}\). These are unequal, whereas the correct forward and reverse flows are both \(\tfrac1{18}\).

A reliable calculation keeps the proposal and acceptance stages separate: first compute \(q(y)\), then multiply by \(\alpha(x,y)\) for an off-diagonal transition, and finally place all rejected probability on the diagonal. Check every transition row sums to \(1\), and, when calculating a stationary distribution, verify \(\pi P=\pi\). In continuous spaces, inspect the ratio \(\pi/q\) in the tails rather than inferring coverage from a few central values. In all cases, the support condition matters: if the proposal assigns zero density to a region with positive target probability, the usual independence sampler cannot reach that region from its proposal mechanism.