Past exam of the probability, statistics and options I course of the University of Oxford / 2010 / S (Simulation)

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 probabilityOtherwise 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.

Start at any integer $x\ge 2$, for example two. Propose $x+1$ or $x-1$ with probability $1/2$ each; if the proposal is one, reject it immediately. Between distinct valid neighboring states the proposal is symmetric. The Metropolis–Hastings acceptance probability for an upward proposal isFor a downward proposal from $x\ge 3$, it isThese are exactly the ratios of the supplied negative binomial distribution probabilities; the factor $p^2$ cancels. The rejection at the boundary supplies a self-loop at two. All neighboring positive states communicate, so the chain is irreducible and aperiodic. Detailed balance gives the desired stationary law. Rejecting the invalid move, rather than forcing an upward move at two, preserves the proposal symmetry used in these ratios.