Past exam of the MSc in advanced computer science course of the University of Oxford / 2021 / Bayesian statistical probabilistic programming / 1 / b / Solution

Here $q(x,y)=p(y)$, with fresh proposal randomness independent of the past. For $x,y\in S$, the Metropolis–Hastings acceptance probability isThus $P(x,y)=p(y)$ is independent of $x$, and $X_1,\dots ,X_N$ are independent and identically distributed random variables with probability distribution $p$, even if $X_0$ was chosen arbitrarily in $S$. The method becomes ordinary Monte Carlo method sampling from $p$. The average of $f(X_1),\dots ,f(X_N)$ is an unbiased estimator, with the variance stated in part (a). Including an arbitrary initial state would spoil this finite-sample property. This is the independent stationary proposal lemma.