Markov Chain Monte Carlo (MCMC)

MCMC - Theory

Problem:

• approximate or sample from target distribution 𝜋

Solution:

• Markov Chain idea: given an ergodic transition matrix 𝑇 there exists a stationary distribution 𝜋
• MCMC idea: given a target distribution 𝜋 construct an ergodic transition matrix 𝑇 that will produce 𝜋
  • the ergodic theorem states that sampling from this Markov chain 𝑇 will approximate the target distribution 𝜋

  • Click here to expand...

    • 𝑙𝑖𝑚_𝑡→∞[𝜂(𝑖,𝑡)/𝑡] = 𝜋(𝑖)

    where:

    • 𝑡 - the number of steps
    • 𝑖 - a state in the Markov chain
    • 𝜂(𝑖,𝑡) - the number of visits to state 𝑖 over a period of 𝑡 steps
    • 𝜋(𝑖) > 0 - the stationary distribution value for state 𝑖

MCMC assumes there is some transition matrix 𝑇 that assigns probabilities from going from one state to another

a necessary condition of 𝑇 is that there must exist a vector 𝜋 that satisfies stationary distribution:

• 𝜋(𝑥_𝑗) = 𝛴_𝑥𝑖𝜋(𝑥_𝑖)𝑇(𝑥_𝑖 → 𝑥_𝑗)
• 𝜋 = 𝜋𝑇 # matrix vector form

example stationary distribution

• 𝜋(𝑥_𝑗) = 𝜋(𝑥₀)𝑇(𝑥₀ → 𝑥_𝑗) + 𝜋(𝑥₁)𝑇(𝑥₁ → 𝑥_𝑗)

for 𝑗=0:

• 𝜋(𝑥₀) ≈ 𝜋(𝑥₀)𝑇(𝑥₀ → 𝑥₀) + 𝜋(𝑥₁)𝑇(𝑥₁ → 𝑥₀)
• 0.571 ≈ 0.571 * 0.7 + 0.428 * 0.4
• 0.571 ≈ 0.5709

for 𝑗=1:

• 𝜋(𝑥₁) ≈ 𝜋(𝑥₀)𝑇(𝑥₀ → 𝑥₁) + 𝜋(𝑥₁)𝑇(𝑥₁ → 𝑥₁)
• 0.428 ≈ 0.571 * 0.3 + 0.428 * 0.6
• 0.428 ≈ 0.4281

Suppose target distribution is a joint distribution over 𝑛 variables 𝐏(𝑋₁, …, 𝑋_𝑛)

In the Markov Chain state-space each state is a complete assignment 𝒙 to 𝑿 = {𝑋₁, …, 𝑋_𝑛}

we traverse the state-space 𝑡 times, thus getting 𝑡 samples {𝒙⁽¹⁾, …, 𝒙^(𝑡)}:

• 𝒙⁽¹⁾ ~ 𝑇(𝒙⁽⁰⁾ → 𝒙⁽¹⁾)
• 𝒙⁽²⁾ ~ 𝑇(𝒙⁽¹⁾ → 𝒙⁽²⁾)
• …
• 𝒙^(𝑡) ~ 𝑇(𝒙^(𝑡-1) → 𝒙^(𝑡))

MCMC gives approximate correlated samples:

• 𝔼_𝐏[𝑓] ≈ (1/𝑡) 𝛴_{1≤𝑖≤𝑡} 𝑓(𝒙^(𝑖))

at a high level, the Markov Chain is defined in terms of a graph of states over which the sampling algorithm takes a random walk. In the case of graphical models, this graph is not the original graph, but rather whose nodes are possible are the possible assignments to our variables {𝑋₁, …, 𝑋_𝑛}. A transition model 𝑇 specifies for each pair of states (𝒙, 𝒙’) the probability 𝑇(𝒙 → 𝒙’) of going from state 𝒙 to 𝒙’.

this defines a random sequence of states: {𝒙⁽¹⁾, …, 𝒙^(𝑡)}. Using chain dynamics we can define distributions over subsequent states:

• 𝐏^(𝑖+1)(𝑋^(𝑖+1)=𝒙’) = 𝛴_𝒙[𝐏^(𝑖)(𝑋^(𝑖)=𝒙)𝑇(𝒙 → 𝒙’)]

intuitively, the probability of being at state 𝒙’ at time 𝑖+1 is the sum over all possible states 𝒙 that the chain could be at time 𝑖 of the probability of being in state 𝒙 times the probability that the chain took a transition from 𝒙 to 𝒙’

as the process converges, we would expect 𝐏^(𝑖+1) to be close to 𝐏^(𝑖):

• 𝐏^(𝑖)(𝒙’) = 𝐏^(𝑖+1)(𝒙’) = 𝛴_𝒙[𝐏^(𝑖)(𝒙)𝑇(𝒙 → 𝒙’)]

at convergence, we expect the resulting distribution 𝜋(𝑿) to be an equilibrium relative to the transition model (i.e. the probability of being in a state is the same as the probability of transitioning into it from a randomly sampled predecessor)

• 𝜋(𝑿=𝒙’) = 𝛴_𝒙𝜋(𝑿=𝒙)𝑇(𝒙 → 𝒙’)

𝜋(𝑿) is a stationary distribution for a Markov Chain 𝑇

MCMC - Transition Models

Click here to expand...

we often define a set of transition models {𝑇₁, 𝑇_𝑘} where each transition model 𝑇_𝑖 is called a kernel.

In certain cases, the variety or multiplicity of kernels:

• is necessary, because no single kernel on its own suffices to ensure regularity
• makes the state-space more connected and therefore speeds up the convergence to a stationary distribution

Methods in Constructing a Markov Chain From Multiple Transition Models

• simply select a random 𝑇_𝑖 from {𝑇₁, 𝑇_𝑘} at each step
• simply cycle through over different transition models at each step

in the case of graphical models, we could define a multi-kernel chain, where we have a kernel 𝑇_𝑖 for each variable/node. Thus 𝑇_𝑖 takes state (𝒙_-𝑖, 𝑥_𝑖) and transitions to a state of the form (𝒙_-𝑖, 𝑥_𝑖’). This method is called Gibbs Sampling

Link to original

MCMC - Implementations

Suppose target distribution is 𝐏(𝑋₁, …, 𝑋_𝑛)

MCMC - Examples

Simple Example

Subpages

• Importance Sampling (IS) vs Monte Carlo Markov Chains (MCMC)

Resources

• https://statswithr.github.io/book/stochastic-explorations-using-mcmc.html