Wait, What?
A simulation can produce millions of numbers and still fail to explore the distribution you wanted.
Markov Chain Monte Carlo (MCMC) is not simply “generate random values until the histogram looks right.” It constructs a dependent sequence whose long-run behaviour targets a probability distribution that may be difficult to sample from directly. The professional skill is to design or select transitions, understand why the target distribution is preserved, diagnose poor exploration and know when the output is not trustworthy.
Quick Answer
Learn MCMC through the route direct sampling → Monte Carlo estimation → Markov chains → stationary distributions → Metropolis proposals → accept/reject correction → Gibbs updates → autocorrelation → effective sample size → multiple chains → R-hat → Hamiltonian Monte Carlo → NUTS → divergences → reparameterisation → professional diagnostics. A beginner should be able to trace one transition. A professional should be able to explain why the chain targets the right distribution and whether it explored that distribution well enough.
1. Start With Ordinary Monte Carlo
If we can draw independent samples X₁,…,Xₙ from a target distribution, we can estimate an expectation by averaging f(X). The uncertainty falls as the number of effective observations increases. This is ordinary Monte Carlo.
MCMC becomes useful when direct independent sampling is hard but we can evaluate the target density up to a normalising constant or condition on parts of the model.
2. A Markov Chain Remembers Only the Current State
In a Markov chain, the distribution of the next state depends on the present state rather than the entire previous path. This does not mean the states are independent. In fact, dependence between neighbouring samples is one of the central practical issues in MCMC.
The learner should first simulate a tiny finite-state chain and watch how repeated transitions change the distribution of states over time.
3. The Target Appears as a Stationary Distribution
An MCMC transition is designed so that the desired target distribution is stationary: if the current state were already distributed according to the target, applying the transition would preserve that distribution.
Stationarity alone is not enough. The chain must also be able to move around the relevant state space rather than become trapped in disconnected or nearly disconnected regions.
4. Metropolis–Hastings Separates Proposal From Correction
The Metropolis–Hastings pattern is conceptually elegant:
- propose a candidate y from a proposal distribution q(y|x);
- compare the target density at y with the density at the current x, correcting for proposal asymmetry when needed;
- accept y with the appropriate probability;
- otherwise remain at x.
The accept/reject step repairs the bias introduced by an imperfect proposal so the target distribution remains invariant.
5. Rejection Is Part of the Algorithm, Not a Failure
Beginners often think a rejected proposal is wasted work. In Metropolis methods, staying at the current state is itself a legitimate transition. The chain’s repeated states are part of the probability law that makes the sampler correct.
The professional question is not “Can I eliminate rejection?” but “Does this proposal produce efficient movement while preserving the target?”
6. Proposal Scale Controls a Real Trade-Off
A proposal that takes tiny steps may be accepted frequently but explore slowly. A proposal that jumps too far may be rejected often. Efficient sampling requires movement through the distribution, not merely a high acceptance rate.
A good exercise is to run the same one-dimensional target with three proposal scales and compare trace plots, autocorrelation and effective sample size.
7. Gibbs Sampling Uses Conditional Distributions
When a multivariate distribution has conditional distributions that are easy to sample, Gibbs sampling updates one variable or block at a time conditional on the others. Each update leaves the joint target invariant.
This makes Gibbs attractive in structured models, but strong dependence between variables can make one-at-a-time updates crawl through a narrow correlated region.
8. Samples Are Correlated, So Raw Draw Count Misleads
If consecutive draws are highly correlated, 10,000 recorded states do not contain the information of 10,000 independent observations. MCMC therefore uses effective sample size (ESS) to estimate how much independent-sample information the chain carries.
Modern Stan tooling distinguishes bulk and tail effective sample sizes because estimating central mass and estimating tail behaviour are different tasks. See Stan posterior diagnostics.
9. Autocorrelation Is a Map of Repeated Information
Autocorrelation measures how strongly a draw predicts later draws at different lags. Slowly decaying autocorrelation signals inefficient exploration. It can arise from poor proposal scale, strong posterior geometry, weak parameterisation or a sampler poorly matched to the target.
10. Warmup Is Adaptation, Not Magical Purification
Introductory descriptions often say “discard burn-in and the rest is fine.” Modern samplers use warmup for more than waiting. They may adapt step sizes, proposal scales or metric information before drawing the retained sample.
The correct learning goal is to understand what adaptation is doing and why the retained draws must come from a fixed post-warmup transition rule with the intended target.
11. Multiple Chains Test Whether Different Starts Reach the Same Region
Running several chains from dispersed initial values helps reveal whether the sampler is consistently exploring the same target region. If chains remain separated, the problem may be multimodality, slow mixing, a poor parameterisation or insufficient sampling.
12. R-hat Compares Within-Chain and Between-Chain Behaviour
R-hat is a convergence diagnostic that compares variation within chains with variation between chains. Modern rank-normalised variants are more robust than older forms. Stan’s current guidance recommends multiple chains and reports improved R-hat together with bulk and tail ESS. See Stan convergence and efficiency diagnostics.
R-hat is not a proof of correctness. It is one diagnostic in a larger evidence bundle.
13. Trace Plots Are Useful but Not Sufficient
A trace plot can reveal sticking, drift, chains occupying different regions or long-range dependence. But a visually “hairy” plot can still hide problems in high dimensions. Numerical diagnostics, predictive checks and model-specific reasoning must complement visual inspection.
14. Hamiltonian Monte Carlo Uses Geometry to Travel Further
Random-walk proposals can waste many steps in high-dimensional continuous targets. Hamiltonian Monte Carlo (HMC) augments the state with momentum and follows approximate Hamiltonian dynamics using gradients of the log density, allowing longer informed moves with an acceptance correction.
Stan’s current reference manual describes HMC and its adaptive No-U-Turn Sampler (NUTS): Stan Reference Manual: MCMC Sampling.
15. Leapfrog Integration Is Approximate by Design
HMC numerically integrates a continuous trajectory using discrete leapfrog steps. The integrator introduces error, and the Metropolis acceptance step corrects that approximation so the intended target is preserved.
This is a useful algorithmic connection: numerical approximation can be embedded inside an exact-in-distribution Monte Carlo correction.
16. NUTS Adapts Trajectory Length
Ordinary HMC requires choosing how many leapfrog steps to take. Too few wastes momentum; too many can retrace the trajectory. NUTS grows trajectories adaptively and stops when continued travel would begin turning back on itself.
Professionals should understand the principle rather than treat “NUTS” as a black-box quality label.
17. Divergences Are Diagnostic Evidence
In HMC, a divergent transition indicates that the numerical trajectory is having difficulty following the target geometry at the chosen step size and parameterisation. Merely collecting more samples does not fix that geometry.
Stan explains divergent transitions as failures of the numerical integration to follow difficult posterior geometry accurately: Stan Reference Manual: Divergent Transitions.
18. Reparameterisation Can Matter More Than More Iterations
If a model creates narrow funnels, extreme correlations or radically different scales, a sampler may struggle no matter how long it runs. Reparameterising the model can reshape the geometry into a form the sampler can explore efficiently.
This is a professional transition from “tune the algorithm harder” to “redesign the representation of the problem.”
19. Randomised Algorithms and MCMC Have Different Jobs
The existing How to Learn Randomized Algorithms article owns random choices, expected running cost, Las Vegas and Monte Carlo guarantees. MCMC uses randomness for a different purpose: constructing dependent samples from a target distribution and quantifying the quality of that approximation.
20. Common Learning Failure States
- Assuming MCMC samples are independent.
- Judging quality only by the number of recorded draws.
- Treating a high Metropolis acceptance rate as automatically good.
- Discarding an arbitrary burn-in period and assuming convergence is solved.
- Running only one chain.
- Reading R-hat as a proof rather than a diagnostic.
- Ignoring effective sample size and tail behaviour.
- Suppressing divergent-transition warnings instead of investigating geometry.
- Assuming more iterations repair a fundamentally poor parameterisation.
21. A Beginner-to-Professional Learning Ladder
- Level 1: estimate a simple expectation with independent Monte Carlo samples.
- Level 2: simulate a finite-state Markov chain and observe its long-run frequencies.
- Level 3: trace a one-dimensional Metropolis update by hand.
- Level 4: compare proposal scales using acceptance and movement.
- Level 5: implement Gibbs sampling for a small conditional model.
- Level 6: compute and interpret autocorrelation and ESS.
- Level 7: run multiple chains and diagnose R-hat.
- Level 8: explain leapfrog integration and HMC acceptance correction.
- Level 9: diagnose divergences and poor parameterisations.
- Level 10: justify sampler choice, diagnostics, stopping evidence and uncertainty reporting for a real model.
22. Teach Transitions Before APIs
Before learners call a probabilistic-programming library, let them trace five to ten transitions on a toy target. Ask them to predict the proposal, acceptance probability, resulting state and whether repeated states must be kept. This creates a mental model for what the library later automates.
Programming-education research supports reducing the write-code burden while the learner is building a new problem-solving schema. Adaptive Parsons problems can offer an intermediate reconstruction step before full implementation; see Hou, Ericson and Wang (ICER 2022). Structured debugging instruction is also important because probabilistic code can run without crashing while still producing invalid inference; see the systematic review Decoding Debugging Instruction.
23. Immediate, Delayed and Transfer Checks
- Immediate: calculate one Metropolis acceptance decision.
- Movement: compare a chain with tiny and oversized proposal steps.
- Dependence: explain why 10,000 correlated draws may contain far less than 10,000 draws of information.
- Delayed: reconstruct Metropolis–Hastings or Gibbs without notes.
- Diagnostic: interpret trace, R-hat, bulk ESS, tail ESS and divergences together.
- Transfer: decide whether direct sampling, importance sampling, Gibbs, random-walk Metropolis or HMC is appropriate for several target geometries.
24. AI Assistance Boundary
AI can explain diagnostics, generate toy targets and help visualise Markov chains. The learner should still be able to derive the logic of a transition, identify dependence, recognise poor mixing, distinguish sample count from effective sample size, and justify whether the resulting approximation is credible.
Professional Direction
Advanced study includes adaptive MCMC, slice sampling, Hamiltonian dynamics, Riemannian methods, sequential Monte Carlo, tempering, multimodal sampling, coupling, unbiased MCMC, particle MCMC and specialised samplers for discrete or constrained spaces. Modern probabilistic-programming systems such as Stan and PyMC automate substantial machinery, but professional use still requires understanding the diagnostics and geometry that determine whether automation succeeded.
Algorithm-learning rule: a sampler is not validated because it ran. Validate the transition, the exploration, the effective information and the geometry before trusting the estimate.
eduKate Sengkang 