Monte Carlo sampling methods using Markov chains and their applications

Inside the paper

The problem

Monte Carlo averages are useful when integrals are difficult, but drawing independent samples from a desired distribution may itself be difficult. A dependent sequence can be easier to generate, although its dependence complicates assessment of error.

The idea

Construct a Markov chain whose equilibrium distribution is the distribution of interest. A proposed move and an acceptance rule together determine the chain, allowing a wider choice of proposals.

How it works

• Choose a transition proposal for moving from the current state to a candidate state.
• Compare the target weights and the probabilities of proposing the forward and reverse moves to calculate an acceptance probability.
• Move to the candidate if accepted; otherwise retain the current state, and repeat the procedure to form a chain.
• Estimate the desired average from states in the chain, allowing for dependence between successive observations when assessing uncertainty.

What it showed

The paper develops a general family of transition rules and relates it to existing sampling methods. It also discusses sources of error and applies Markov-chain sampling to generating random orthogonal matrices.

Read it for

Section 2 contains the transition construction and the discussion of convergence and sampling error. Read Section 3 for the matrix application, or skim it on a first pass if your immediate interest is the sampling method.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.