Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 37 / 5

Let $P$ be the transition kernel of the Markov chain. It is phi-irreducible if there is a nonzero sigma-finite measure $\phi$ such that, for every measurable $A$ and every starting state $x$,Equivalently, there is positive probability of eventually reaching every set of positive reference measure. For a finite state space with counting measure, this becomes ordinary irreducible Markov chain accessibility. On a continuous space, requiring access to each individual point would usually be inappropriate; positive-measure sets play that role. Irreducibility requires positive probability, rather than probability one, and does not itself assert recurrence or a finite mean return time.

A convenient general-state-space ergodic theorem is the following. For a positive Harris recurrent Markov chain with invariant probability measure $\pi$, and a measurable function $h$ with $\pi |h|<\infty$,Here $\pi h=\int hd\pi$ is the stationary expected value. Harris recurrence means that every set of positive irreducibility measure is visited almost surely from every state; positive recurrence supplies an invariant probability rather than only an infinite invariant measure. The ergodic theorem for a positive Harris recurrent Markov chain holds from any starting state under these Harris hypotheses. aperiodicity is not necessary just for averages.

A useful sufficient form of the central limit theorem for a geometrically ergodic Markov chain adds aperiodicity, geometric ergodicity, and $\pi (|h{|}^{2+\delta })<\infty$ for some $\delta >0$. It givesThese are sufficient hypotheses, not a claim that irreducibility alone ensures a central limit theorem. The Markov chain Monte Carlo asymptotic variance uses stationary covariances ${\gamma }_h(k)={\mathrm{Cov}}_{\pi }(h(X_0),h(X_k))$, with ${\gamma }_h(0)={\mathrm{Var}}_{\pi }h$. The series is absolutely convergent under the stated sufficient assumptions. If ${\gamma }_h(0)>0$, write ${\rho }_h(k)={\gamma }_h(k)/{\gamma }_h(0)$ and $v_h={\gamma }_h(0){\tau }_{\mathrm{int}}$, where the integrated autocorrelation time is ${\tau }_{\mathrm{int}}=1+2{\sum }_{k\ge 1}{\rho }_h(k)$. When $v_h>0$, the effective sample size of a Markov chain is approximately $n/{\tau }_{\mathrm{int}}$. Negative correlations can reduce the asymptotic variance; a zero asymptotic variance gives a degenerate normal limit. For constant $h$, variance is zero and the autocorrelation normalization is undefined.

First require a proper target: $0<Z={\int }_{{\mathbb{R}}^d}\pi (x)dx<\infty$ and $\bar{\pi }=\pi /Z$. The Metropolis–Hastings algorithm uses the Metropolis–Hastings acceptance probabilitySufficient general conditions are phi-irreducibility, aperiodicity, and a drift-minorisation condition establishing geometric ergodicity of the resulting chain, together with a stationary $(2+\delta )$th moment for the observable being averaged. These imply the central limit theorem for a geometrically ergodic Markov chain. The observable's moment condition must be included: conditions on the sampler alone cannot give the theorem for every arbitrary function.

A concrete stronger condition, directly in terms of the proposal, isTogether with a bounded observable, this is an especially simple sufficient answer. The accepted proposal density is $\min \{q(y\mid x),\bar{\pi }(y)q(x\mid y)/\bar{\pi }(x)\}$, so it is at least $ϵ\bar{\pi }(y)$. The kernel satisfies a global minorization condition with the target, hence uniform geometric ergodicity, positive Harris recurrence, and aperiodicity. An independent proposal whose importance weight $\bar{\pi }(y)/q(y)$ is uniformly bounded is one example. No claim of these properties follows merely from writing down a positive proposal.

The algorithm is a Random-scan Gibbs sampler. Start at a point where the target is positive, with a proper normalizing integral and well-defined full conditional distributions. Its state is the entire coordinate vector. Choosing the initial point fixes the initial law; it need not already be the invariant law. The transition rule below preserves the target irrespective of this choice.

At each transition, choose a coordinate uniformly and independently of the previous coordinate choices. Draw a fresh value from that coordinate's full conditional distribution given the current remaining coordinates, and keep all other coordinates fixed. This supplies the random-selection and conditional-draw operations lost in the TeX transcription. The update depends only on the current vector and fresh randomness, which proves the Markov property. The printed mathematical requests are the kernel and its detailed balance, answered in the following two subsections.

For the Random-scan Gibbs sampler, the correct transition kernel is a measure, since a one-coordinate update is singular with respect to full-dimensional Lebesgue measure when $p>1$. Write $x_{-i}$ for all coordinates except $i$. ThenEach Dirac measure fixes an unupdated coordinate. Equivalently, $P(x,A)=p^{-1}{\sum }_i\int 1_A(x_{-i},z){\pi }_i(z\mid x_{-i})dz$, with $z$ placed in coordinate $i$. Replacing this kernel by an ordinary density on the whole product space would omit those fixed-coordinate constraints.

Let $\bar{\pi }$ be the normalized target and ${\bar{\pi }}_{-i}$ its marginal distribution. A coordinate-$i$ kernel $P_i$ leaves $x_{-i}=x_{-i}^{\prime }$ and has the joint old-new measureThis is symmetric in the old and new state: the common remaining coordinates are fixed and the two conditional factors exchange places. Thus each coordinate kernel satisfies detailed balance. Averaging them with the fixed weights $1/p$ provesIntegrating out the old state proves invariance of $\bar{\pi }$. The common normalization cancels, so detailed balance can also be written with the unnormalized target. This establishes detailed balance of a random-scan Gibbs sampler and a reversible Markov chain. Fresh independent random choices make the update a Markov chain, as explained above; invariance is not an assertion that an arbitrarily initialized chain starts in stationarity.