The wall the earlier methods hit
Look back at everything this rung has done. Inverse-transform and rejection sampling turned a uniform stream into samples from a distribution; Monte Carlo integration averaged a function over those samples; importance sampling reshaped where the samples land to shrink the variance. Every one of these quietly assumed the same thing: that you can draw independent samples directly from the distribution you care about. For a bell curve or an exponential, fine. But the distributions that drive real science break that assumption hard.
The canonical example is Bayesian statistics. You have a posterior distribution over, say, fifty parameters, and you can write down a formula p(x) that is proportional to the density at any point x — but only proportional. The true density is p(x) = g(x) / Z, where g(x) is the easy part you can compute and Z is a normalizing constant equal to the integral of g over all fifty dimensions. That integral is exactly the high-dimensional beast the curse of dimensionality makes uncomputable. So you are stuck twice over: you cannot find Z, and even if you could, there is no inverse-transform formula for a fifty-dimensional custom distribution.
Rejection sampling does not rescue you either. To use it you need an envelope that sits above the density everywhere, and in high dimensions almost every proposed point lands in a region of near-zero density and gets rejected — the acceptance rate collapses toward zero as the dimension grows. We need a fundamentally different idea: a way to wander through the distribution that needs only the ratio g(x') / g(x) at two nearby points, never the dreaded constant Z, and never a global envelope. That idea is Markov-chain Monte Carlo, or MCMC.
A random walk that remembers where it is
A Markov chain is a sequence of states x_0, x_1, x_2, ... where each next state is drawn at random using only the current state — the chain has no memory beyond where it stands right now. Picture a walker stepping around a landscape, deciding each move from its present footing alone. You met this skeleton already without the name: a stationary iteration like x_{n+1} = M x_n + c is a deterministic chain, and its long-run behaviour was governed by a spectral radius. MCMC makes the step random instead of fixed, and asks the mirror-image question.
Here is the key fact that makes the whole method possible. Many Markov chains, if you let them run long enough, forget their starting point and settle into a stationary distribution — a fixed probability of being found at each state, no matter where they began. The fraction of time the walker spends in any region stops depending on where it started and converges to a fixed shape. MCMC turns this around with audacious cleverness: instead of taking a chain and asking what its stationary distribution is, we design the chain backwards so that its stationary distribution is exactly the p(x) we wanted to sample from.
Once the chain is built, the payoff is direct. Run the walker for a long time and simply collect the states it visits: x_1, x_2, ..., x_N. By construction these are samples from p(x) — exactly what inverse-transform and rejection could not give you in high dimensions. You then estimate any expectation the same way Monte Carlo always did, by averaging your function over the collected states. The whole edifice rests on one question: how do we engineer a random step whose stationary distribution lands on the p we chose? The answer is a rule of disarming simplicity.
Metropolis-Hastings: propose, then accept or reject
The Metropolis-Hastings algorithm builds the step out of two moves. From the current point x, first propose a candidate x' by some easy random rule — most simply, take a small Gaussian step, x' = x + (a little random nudge). Then decide whether to accept the move by comparing densities. Crucially, the decision uses only the ratio g(x') / g(x), and in that ratio the unknown constant Z cancels perfectly: g(x')/Z divided by g(x)/Z is just g(x')/g(x). The thing we could never compute simply disappears. That single cancellation is the secret engine of the whole method.
Metropolis (symmetric proposal), one step:
propose: x' = x + step * randn() # random nudge from x
ratio : r = g(x') / g(x) # Z cancels — never needed
accept : if r >= 1 -> move to x' (uphill: always)
else with prob r -> move to x' (downhill: sometimes)
otherwise -> stay at x (count x AGAIN)
record the current state (x' or the repeated x), then repeat.Read the rule plainly. If the candidate sits where the density is higher (r >= 1), always move there — the walker climbs toward the bulk of the probability. If it is lower, still move sometimes, with probability exactly r: a candidate half as likely is accepted about half the time. This gentle willingness to step downhill is what lets the chain explore the whole distribution instead of crawling to the single highest point and freezing — the same temptation that traps a naive optimizer. Why this exact ratio works is a one-line condition called detailed balance: it guarantees that once the chain reaches p(x), each step leaves p(x) unchanged, so p is the stationary distribution we were after.
A close cousin worth a sentence is Gibbs sampling, the natural choice when your distribution is high-dimensional but you happen to know each coordinate's conditional distribution given all the others. Instead of nudging the whole vector at once, Gibbs updates one coordinate at a time, redrawing x_1 given everything else, then x_2, and so on around the cycle. It is really Metropolis-Hastings with a cleverly chosen proposal whose acceptance is always 1 — every move is taken. When the conditionals are tractable, Gibbs sidesteps the awkward business of tuning a step size.
The price of correlated samples
MCMC buys you samples from impossible distributions, but it charges a real fee, and honesty about it is the whole point of this section. The samples are not independent. Because each state is a small nudge from the last, consecutive states are strongly correlated — the walker at step 1001 is right next to where it stood at step 1000. The plain Monte Carlo error law you learned, where error falls like O(1/sqrt(N)), assumed independent draws. With correlated draws, N samples carry less information than N independent ones, so your effective sample size is smaller — sometimes dramatically smaller — than the raw count N.
How fast the chain shakes off its correlations and roams the whole distribution is called its mixing — see mixing time. A well-mixing chain explores quickly and its samples behave almost like independent ones; a badly-mixing chain shuffles in place, perhaps trapped in one mode of a multi-peaked distribution, leaving other regions barely visited even after a million steps. Mixing is governed by the same kind of quantity as ordinary iterations: the second-largest eigenvalue of the chain's transition operator, a direct echo of the spectral radius that set the speed of stationary iterations in the linear-systems rung. Closer to 1, slower mixing.
Tuning ties these threads together. The proposal step size is a balancing act: nudge too small and almost every move is accepted but the walker inches along, barely moving and mixing terribly; nudge too large and the candidates land in low-density wilderness, almost everything is rejected, and the walker sits still. The sweet spot accepts a healthy fraction of moves — folklore for random-walk Metropolis puts it near 23% acceptance in high dimensions, which surprises people who expect higher is better. Get this wrong and the chain still converges eventually, in theory; in practice 'eventually' can outlast your patience and your compute budget.
What MCMC is, honestly
Step back and see the shape of the achievement. MCMC lets you draw samples from a distribution you can only evaluate up to an unknown constant, in dimensions where every other method in this rung simply fails. It needs nothing but the ability to compute the ratio g(x')/g(x) — no normalizing integral, no global envelope, no inverse formula. That is why it became the engine of modern Bayesian computation and of statistical physics, where the unreachable constant Z is the rule, not the exception. When you read that a model was 'fit with MCMC', this random walk with an accept/reject rule is precisely what ran.
And keep the honest limits in view. MCMC is asymptotically correct but offers no clean finite-sample error bar: you never know you have mixed, you only fail to find evidence that you have not. It can stall for ages in a single mode of a multi-peaked distribution and quietly report a confident, wrong answer. The samples are correlated, so the raw N overstates your information. None of this makes the method less remarkable — it makes it a tool to wield with care. Used well, with diagnostics and a healthy suspicion of your own chains, it reaches distributions that were flatly out of reach for everything else you have learned.