Homepage > MCMC
Markov Chain Monte Carlo
  • Concept of Distribution
  • Monte Carlo Simulation
  • Markov Chain
  • Metropolis Algorithm
    Gibbs Sampler
  • Dynamics of Gibbs Models
  • Gibbs Distribution
  • Ising and Potts Models
    Bayesian Models
  • Joint Distribution
  • Frequentist Approach
  • Bayesian Approach
  • Dirichlet Distribution
  • Mixture Model
  • MCMC scheme
    Data Mining and MCMC
  • Relative Report Rate
  • Graphical Model
  • MCMC scheme
    Explore MCMC with R
  • Normal Mixture
  • Searching for Maxima
  • Bernoulli Trials
  • Random Beta Walk
  • Metropolis Algorithm
  • Potts Model

    • 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