Homepage > MCMC

Monte Carlo Simulation

When the probability density function (PDF) $ \pi(x)$ is completely known, the statistical characteristics (mean, variance, etc) of distribution can be obtained in the form of integration

$\displaystyle \int h(x) \pi(x) dx
$

The objective of Monte Carlo simulation is to understand how to sample a random variable $ X$ from the ``target'' PDF $ \pi(x)$.

Monte Carlo integration. Monte Carlo simulation is used to approximate the integration by drawing a large number $ X_1,X_2,\ldots,X_n$ of random variables from $ \pi$.

$\displaystyle \int h(x) \pi(x) dx \approx \dfrac{1}{n} \sum_{i=1}^n h(X_i)
$

Sampling via probability inverse transform. Let $ \Pi(x)$ be a cumulative distribution function (cdf) on the real line $ \mathbb{R}$. Then we can define the quantile function by

$\displaystyle \Pi^{-1}(u) := \sup\left\{ z: \Pi(z) \le u \right\}
$

Algorithm.

  1. Generate an uniform random variable $ \mathbf{U}$ on $ [0,1)$.
  2. Return the value $ X = \Pi^{-1}(\mathbf{U})$.

Rejection sampling methods. Sample first from a different distribution $ \rho(x)$ which satisfies

$\displaystyle \pi(x) \le c \rho(x)$    for all $ x$. $\displaystyle $

Algorithm.

  1. Generate a random variable $ \mathbf{X}$ from $ \rho(x)$.
  2. Generate an uniform random variable $ \mathbf{U}$ on $ [0,1)$.
  3. Accept $ X = \mathbf{X}$ if $ \displaystyle \mathbf{U} \le \frac{\pi(\mathbf{X})}{c \rho(\mathbf{X})}$; otherwise, reject it.

Emergence of Markov chain Monte Carlo simulation. In reality the ``state'' space for $ \pi(x)$ is not $ \mathbb{R}$. Either it is a subset of $ \mathbb{R}^n$ (in Bayesian applications), or it has a complex discrete structure (e.g., Ising model). For such models both algorithms via inverse probability transform and resampling method are not applicable in general. By way of Markov chain convergence theorem one can construct a Markov chain $ \mathbf{X}$ whose stationary distribution is $ \pi$.

\fbox{\rule[-0.2in]{0in}{0.6in}\hspace{0.1in}$\displaystyle
\mathbf{X}_t \stac...
...htarrow} \pi
\quad\mbox{ as }\quad t \longrightarrow \infty.
\hspace{0.1in}$}
This methodology gives a way to break the limitation of Monte Carlo simulation.


© TTU Mathematics