= Solution
{c}
For the <Metropolis–Hastings algorithm>, choose a proposal transition $q(x,y)$ and initialize at a state with $\pi(x)>0$. From current $x$, propose $Y\sim q(x,\cdot)$ and accept it with <probability>
$$
\boxed{\alpha(x,Y)=\min\left\{1,\frac{\pi(Y)q(Y,x)}{\pi(x)q(x,Y)}\right\}.}
$$
Otherwise stay at $x$. The accepted off-diagonal transition satisfies <detailed balance>, since $\pi(x)q(x,y)\alpha(x,y)=\min\{\pi(x)q(x,y),\pi(y)q(y,x)\}$ is symmetric in $x,y$. Thus $\pi$ is stationary. For convergence from arbitrary starting states in the support, choose the proposal so the resulting chain is <irreducible> and aperiodic. Only ratios of target probabilities are needed, so an unknown normalizing constant cancels.
Back to article page
