Markov chain Monte Carlo sampling

Inverse CDF sampling

A simple sampling method adopted by many of the standard math libraries is the inverse probability transform: draw $u\sim \text{Unif}(0,1)$, then draw $x\sim F^{-1}(u)$, where $F^{-1}$ is the inverse of the CDF $F$. Show that $x$ is distributed according to $F$. What is the drawback of this method?

Solution

We let $U$ represent the uniform random variable and start with the fact that $$p(U\le u)=u$$

Showing that $x$ is distributed according to $F$ can be done by showing that $F(x)=p(F^{-1}(U)\le x)$.

So,

And we’re done.

The drawback is that we do not always have the inverse CDF in an analytically tractable form; hence, the need for methods like Markov chain Monte Carlo (MCMC).

Combining multiple stationary distributions

Show that if both transition kernels $K_1$ and $K_2$ have $p(\cdot )$ as stationary density, so do $K_1{K}_2$ and $\lambda K_1+(1-\lambda )K_2$. In practice, the former corresponds to sampling from $K_1$ and $K_2$ cyclically and the latter draws either $K_1$ with probability $\lambda$ or $K_2$ otherwise. Although it is not required to show, extension to more than two kernels should be straightforward.

In the continuous case, the cyclic kernel can be defined as composition of functions:

$$(K_1\circ K_2)(z|x)=\int K_2(y|x)K_1(z|y)\mathrm{d}y$$

Solution

Cyclic sampling

Discrete

We let $\pi$ be the vector of probabilities of the stationary distribution and $K$ a matrix where $K_{ji}$ represents the transition probability from $x_i$ to $x_j$.

Continuous

Sampling with a mixture of kernels

Discrete

Continuous

Metropolis-Hastings sampling produces a stationary distribution equal to the target

Recall MH sampling for target distribution $p(x)$ using proposal $q(x|y)$: at state $s$, first draw $t\sim q(t|s)$, then accept t with probability $$A(t|s)=min(1,\frac{\tilde{p}(t)q(s|t)}{\tilde{p}(s)q(t|s)})$$

where $p(x)$ is the unnormalized target distribution. Show that $p(x)$ is the stationary distribution of the Markov chain defined by this procedure.

Consider both continuous and discrete cases.

Solution

We will show that the detailed balance equation $p(t)T(s|t)=p(s)T(t|s)$ is satisfied, which implies that $p(x)$ is the stationary distribution of the Markov chain (see Koller & Friedman¹, Proposition 12.3).

This holds for both continuous ($p(t)={\int }_{s}p(s)T(t|s)ds$) and discrete ($p(t)=\sum _{s}p(s)T(t|s)$) state spaces.

When $s\ne t$

When $s=t$

Though $T(s|t)$ has a different form when $s=t$, it does not matter. The proof is trivial; we can simply exchange $s$ and $t$ on one side to get the other: $$\boxed{p(s)T(t|s)=p(s)T(s|s)=p(t)T(s|t)}$$

Gibbs sampling produces a stationary distribution equal to the target

Recall Gibbs sampling for target distribution $p(x)=p(x_1,\dots ,x_d)$: for each $j\in 1,\dots ,d$, draw $t\sim p(x_j|\mathsf{\text{rest}})$ and set $x_j=t$. Show that $p(x)$ is the stationary distribution of the Markov chain defined by this procedure.

Solution

Again, we prove that the detailed balance equation holds; in the case of Gibbs case, it is

where $T(x_{-j},x_j^{\prime }|x_{-j},x_j)=p(x_j^{\prime }|x_{-j})$ and $x_{-j}=\{x_i:i\ne j\}$.

We start with the left side and show it is equal to the right: