11.2 The two basic 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

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

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

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

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

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

We can rewrite this as

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

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<U<\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}$.