Overview

The pCN algorithm generates a Markov chain ${\displaystyle (X_{n})_{n\in \mathbb {N} }}$ on a Hilbert space ${\displaystyle {\mathcal {H}}}$ whose invariant measure is a probability measure ${\displaystyle \mu }$ of the form

${\displaystyle \mu (E)={\frac {1}{Z}}\int _{E}\exp(-\Phi (x))\,\mu _{0}(\mathrm {d} x)}$

for each measurable set ${\displaystyle E\subseteq {\mathcal {H}}}$, with normalising constant ${\displaystyle Z}$ given by

${\displaystyle Z=\int _{\mathcal {H}}\exp(-\Phi (x))\,\mu _{0}(\mathrm {d} x),}$

where ${\displaystyle \mu _{0}={\mathcal {N}}(0,C_{0})}$ is a Gaussian measure on ${\displaystyle {\mathcal {H}}}$ with covariance operator ${\displaystyle C_{0}}$ and ${\displaystyle \Phi \colon {\mathcal {H}}\to \mathbb {R} }$ is some function. Thus, the pCN method applied to target probability measures that are re-weightings of a reference Gaussian measure.

The Metropolis–Hastings algorithm is a general class of methods that try to produce such Markov chains ${\displaystyle (X_{n})_{n\in \mathbb {N} }}$, and do so by a two-step procedure of first proposing a new state ${\displaystyle X'_{n+1}}$ given the current state ${\displaystyle X_{n}}$ and then accepting or rejecting this proposal, according to a particular acceptance probability, to define the next state ${\displaystyle X_{n+1}}$. The idea of the pCN algorithm is that a clever choice of (non-symmetric) proposal for a new state ${\displaystyle X'_{n+1}}$ given ${\displaystyle X_{n}}$ might have an associated acceptance probability function with very desirable properties.

The pCN proposal

The special form of this pCN proposal is to take

${\displaystyle X'_{n+1}={\sqrt {1-\beta ^{2}}}X_{n}+\beta \Xi _{n+1},}$

${\displaystyle \Xi _{n+1}\sim \mu _{0}{\text{ i.i.d.}}}$

or, equivalently,

${\displaystyle X'_{n+1}|X_{n}\sim {\mathcal {N}}\left({\sqrt {1-\beta ^{2}}}X_{n},\beta ^{2}C_{0}\right).}$

The parameter ${\displaystyle 0<\beta <1}$ is a step size that can be chosen freely (and even optimised for statistical efficiency). One then generates ${\displaystyle Z_{n+1}\sim \mathrm {Unif} ([0,1])}$ and sets

${\displaystyle X_{n+1}=X'_{n+1}{\text{ if }}Z_{n+1}\leq \alpha (X_{n},X'_{n+1}),}$

${\displaystyle X_{n+1}=X_{n}{\text{ if }}Z_{n+1}>\alpha (X_{n},X'_{n+1}).}$

The acceptance probability takes the simple form

${\displaystyle \alpha (x,x')=\min(1,\exp(\phi (x)-\phi (x'))).}$

It can be shown^[2] that this method not only defines a Markov chain that satisfies detailed balance with respect to the target distribution ${\displaystyle \mu }$, and hence has ${\displaystyle \mu }$ as an invariant measure, but also possesses a spectral gap that is independent of the dimension of ${\displaystyle {\mathcal {H}}}$, and so the law of ${\displaystyle X_{n}}$ converges to ${\displaystyle \mu }$ as ${\displaystyle n\to \infty }$. Thus, although one may still have to tune the step size parameter ${\displaystyle \beta }$ to achieve a desired level of statistical efficiency, the performance of the pCN method is robust to the dimension of the sampling problem being considered.

Contrast with symmetric proposals

This behaviour of pCN is in stark contrast to the Gaussian random walk proposal

${\displaystyle X'_{n+1}\mid X_{n}\sim {\mathcal {N}}\left(X_{n},\beta \Gamma \right)}$

with any choice of proposal covariance ${\displaystyle \Gamma }$, or indeed any symmetric proposal mechanism. It can be shown using the Cameron–Martin theorem that for infinite-dimensional ${\displaystyle {\mathcal {H}}}$ this proposal has acceptance probability zero for ${\displaystyle \mu }$-almost all ${\displaystyle X'_{n+1}}$ and ${\displaystyle X_{n}}$. In practice, when one implements the Gaussian random walk proposal in dimension ${\displaystyle N}$, this phenomenon can be seen in the way that

• for fixed ${\displaystyle \beta }$, the acceptance probability tends to zero as ${\displaystyle N\to \infty }$, and
• for a fixed desired positive acceptance probability, ${\displaystyle \beta \to 0}$ as ${\displaystyle N\to \infty }$.