\[ \newcommand{\Exg}{\operatorname{\mathbb{E}}} \newcommand{\Ex}{\mathbb{E}} \newcommand{\Ind}{\mathbb{I}} \newcommand{\Var}{\operatorname{Var}} \newcommand{\Cov}{\operatorname{Cov}} \newcommand{\Corr}{\operatorname{Corr}} \newcommand{\ee}{\mathrm{e}} \]

19  Metropolis–Hastings in discrete space

Summary:

• The Metropolis–Hastings algorithm gives a way of designing a Markov chain whose stationary distribution is a given PMF \(\pi\).

• We make proposal moves according to a transition matrix \(\mathsf R = (r(x,y))\). A proposal move from \(x\) to \(y\) is accepted with probability \[\alpha(x,y) = \min \left\{ \frac{\pi(y)\,r(y,x)}{\pi(x)\,r(x,y)} , \, 1\right\} . \]

• The most important example is the random walk Metropolis algorithm, where \(`mathsf R\) is the transition matrix of the simple symmetric random walk and \[\alpha(x,y) = \min \left\{ \frac{\pi(y)}{\pi(x)} , \, 1\right\} . \]

Read more: Voss, An Introduction to Statistical Computing, Subsection 4.1.2.