11.2 The two basic schemes

We will present general definitions and discussion in the context of finite-state chains on a state space $S$; translating to continuous state space such as $R^{d}$ involves slightly different notation without any change of substance.

11.2.1 Metropolis schemes

Write $K=(k_{xy})$ for a proposal transition matrix on $S$. The simplest case is where $K$ is symmetric ($k_{xy}\equiv k_{yx}$). In this case, given $\pi$ on $S$ we define a step $x\to x^{\prime}$ of the associated Metropolis chain in words by

• pick $y$ from $k(x,\cdot)$ and propose a move to $y$;

• accept the move (i.e. set $x^{\prime}=y$) with probability $\min(1,\pi_{y}/\pi_{x})$, otherwise stay ($x^{\prime}=x$).

This recipe defines the transition matrix $P$ of the Metropolis chain to be

 $p_{xy}=k_{xy}\min(1,\pi_{y}/\pi_{x}),\quad y\neq x.$

Assuming $K$ is irreducible and $\pi$ strictly positive, then clearly $P$ is irreducible. Then since $\pi_{x}p_{xy}=k_{xy}\min(\pi_{x},\pi_{y})$, symmetry of $K$ implies $P$ satisfies the detailed balance equations and so is reversible with stationary distribution $\pi$.

The general case is where $K$ is an arbitrary transition matrix, and the acceptance rule becomes

• accept a proposed move $x\to y$ with probability $\min(1,\frac{\pi_{y}k_{yx}}{\pi_{x}k_{xy}})$.

The transition matrix of the Metropolis chain becomes

 $p_{xy}=k_{xy}\min\left(1,\frac{\pi_{y}k_{yx}}{\pi_{x}k_{xy}}\right),\quad y% \neq x.$ (11.5)

To ensure irreducibility, we now need to assume connectivity of the graph on $S$ whose edges are the $(x,y)$ such that $\min(k_{xy},k_{yx})>0$. Again detailed balance holds, because

 $\pi_{x}p_{xy}=\min(\pi_{x}k_{xy},\pi_{y}k_{yx}),\quad y\neq x.$

The general case is often called Metropolis-Hastings – see Notes for terminological comments.

11.2.2 Line-sampling schemes

The abstract setup described below comes from Diaconis [124]. Think of each $S_{i}$ as a line, i.e. the set of points in a line.

Suppose we have a collection $(S_{i})$ of subsets of state space $S$, with $\cup_{i}S_{i}=S$. Write $I(x):=\{i:x\in S_{i}\}$. Suppose for each $x\in S$ we are given a probability distribution $i\to w(i,x)$ on $I(x)$, and suppose

 $x,y\in S_{i}$ (11.6)

Write $\pi^{[i]}(\cdot)=\pi(\cdot|S_{i})$. Define a step $x\to y$ of the line-sampling chain in words by

• choose $i$ from $w(\cdot,x)$;

• then choose $y$ from $\pi^{[i]}$.

So the chain has transition matrix

 $p_{xy}=\sum_{i\in I(x)}w(i,x)\pi^{[i]}_{y},\quad y\neq x.$

We can rewrite this as

 $p_{xy}=\sum_{i\in I(x)\cap I(y)}w(i,x)\pi_{y}/\pi(S_{i})$

and then (11.6) makes it clear that $\pi_{x}p_{xy}=\pi_{y}p_{yx}$. For irreducibility, we need the condition

 the union over $i$ of the edges in the complete graphs
 $S_{i}$ (11.7)

Note in particular we want the $S_{i}$ to be overlapping, rather than a partition.

This setting includes many examples of random walks on combinatorial sets. For instance, card shuffling by random transpositions (yyy cross-ref) is essentially the case where the collection of subsets consists of all $2$-card subsets. In the $R^{d}$ setting, with target density $f$, the Gibbs sampler is the case where the collection consists of all lines parallel to some axis. Taking instead all lines in all directions gives the hit-and-run sampler, for which a step from $x$ is defined as follows.

• Pick a direction uniformly at random, i.e. a point $y$ on the surface on the unit ball.

• Step from $x$ to $x+Uy$, where $-\infty is chosen with density proportional to

 $u^{d-1}f(x+uy).$

The term $u^{d-1}$ here arises as a Jacobean; see Liu [237] Chapter 8 for explanation and more examples in $R^{d}$.