We want to know the posterior distribution $P(\theta)$ and where modes are, this is the goal.

1. But we cannot calculate $P(\theta)$ analytically, this is the problem.
2. However, we can build a Markov Chain.
3. Sampling from the Markov Chain builds the histogram, and
4. The histogram approximates $P(\theta)$, this is the solution.

Surprisingly (For Metropolis Hastings) :

• Prior can be an arbitrary normal distribution, although the choice impacts.
• Proposal can be arbitrary normal distribution whose mean is current $\theta $.

The questions and confusions may be:

1. How come arbitrary normal distribution can be used as the prior?
2. How come the chance of transition from $\theta_i$ to $\theta_j$ in the Markov Chain $$q(\theta_j | \theta_i) \times \min\left(1, \frac { \textrm{prior}(\theta_j) \times L(E|\theta_j) \times q(\theta_i | \theta_j)} { \textrm{prior}(\theta_i) \times L(E|\theta_i) \times q(\theta_j | \theta_i)} \right) $$ can be equivalent with $P(\theta_j|\theta_i)$?

Analogy

• There is a mountain and you want to know the approximate shape and where the peaks are, this is the goal.

• But you cannot see nor measure the mountain, this is the problem.

• You have a GPS so you know the coordinate of wherever you go, and you know you are climbing or descending when you make a next step.

Now, you do the random walk over the mountain, and plot $\theta_t = (latitude, longitude)$ every step you make, but you follow one rule: Climb more often than descend.

After 100,000,000 steps, the density of the plots tells where the peaks are, and the rough idea of the shape of the mountain.

What can be confusing when learning MCMC

Text book or article that:

1. Immediately starts with math formulas on how to do MCMC with no intuition nor idea behind explained. If we understand the ideas first, we can derive the math formulas. But it is super hard to reverse-engineer the ideas and intuitions from math formulas.

2. Does not give the intuition or analogy that a probability distributions with modes is similar to a mountain with peaks, and generate more samples around the modes is the essence of MCMC which is equivalent with visiting the mountain peaks more by tending to climb more than descend in the mountain random-walk.

3. Does not explain how and why we can build a Markov Chain that generates samples which approximates $P(\theta)$, and how the detailed balance condition plays the role there.

4. Does not explain the role of proposal distribution q, which is simulating the transition from state $\theta_i$ to $\theta_j$ in the Markov Chain.

5. Does not explain why we can use a normal distribution as $prior(\theta)$.

Related

• Youtube video Markov Chain Monte Carlo gives the intuition that MCMC is like a mountain trekking to figure out the shape by random-walk the mountain. Having such concrete image will give the foundation to understand what MCMC is.

• Real-life example in which Markov chain Monte Carlo is desirable? gives several links to the real life examples.

• The Markov Chain Monte Carlo Revolution and CS168: The Modern Algorithmic Toolbox Lecture #14: Markov Chain Monte Carlo gives the MCMC application to cryptography.

• Decrypting Substitution Cyphers provides the implementation of the MCMC application to cryptography.

• MCMC Explained and Applied to Logistic Regression provides the MCMC implementation of logistic regression to find the parameters to fit the model.