# Why Sampling Beats Solving A probability model is trivial to **write down** (`p(x) ~ exp(-E(x))`) but almost never possible to **compute exactly** — the normalizing constant is an integral over all of input space, which blows up combinatorially with dimension. Three tasks contrasted on one messy landscape: - **Exact integration** — compute the normalizer `Z`. *Intractable* in high dimensions: more terms than atoms in the universe. - **Optimization** — find the peak / mode. *Misleading*: the peak says nothing about how wide the mass is or where the bulk sits. - **Sampling** — draw points proportional to the surface; the cloud of points *reveals the shape* without ever computing `Z`. Sampling is the only strategy that scales, and it is what **Markov Chain Monte Carlo (MCMC)** delivers. The rest of the lesson builds the machinery that makes those samples appear — random walks (<ref slide="2">Random Walks With Memory</ref>), targeting a distribution (<ref slide="3">From Chain To Target</ref>), the Metropolis rule (<ref slide="4">Metropolis Acceptance Rule</ref>), and the cost tradeoffs (<ref slide="7">Compute Cost And Tradeoffs</ref>) that make MCMC the workhorse of modern statistics and AI. ## Random Walks With Memory A **Markov chain** is a random process that moves from one state to another using only the current state to decide what happens next. That “memory” is very limited: the next step depends on where you are now, not on the full history. Even so, the repeated motion can produce rich long-run behavior. The key intuition is that local transition rules can create a global pattern. If some states are easier to enter than leave, the chain will visit them more often over time. That long-run pattern is the **stationary distribution**. In MCMC, you design the chain so that this stable visitation pattern matches the probability distribution you want to sample from. <viz id="1"></viz> **Adjust the transition probabilities** from a few nodes, then **press play**. **Compare the moving particle to the visit histogram** and notice that the path looks noisy step by step, but the visit frequencies settle into a more stable pattern. This is one of the most important conceptual jumps in MCMC. You do not need every sample to be independent. Instead, you accept a correlated sequence of states, as long as its long-run frequency matches the target distribution. From a programming perspective, think of the chain as an iterator with state: each output depends on the previous one, but the aggregate behavior is what matters. That aggregate view leads directly to the central design problem: how do you choose transitions so the chain converges to the distribution you actually want? That is the focus of <ref slide="3">From Chain To Target</ref>. ## From Chain To Target In MCMC, the goal is not just to build any random walk. You want a chain whose **stationary distribution** equals a chosen **target distribution**. That target might be a posterior over model parameters, a latent-variable configuration, or any probability landscape that is easy to evaluate up to a constant factor. The clever part is that the chain can recover the target without drawing independent samples directly. If the transition rule is designed correctly, the walker will spend more time in dense regions and less time in sparse ones. Over many steps, the cloud of visited points begins to resemble the target itself. <viz id="2"></viz> **Run the walker** and **watch both panels together**. Then **adjust the transition controls** and see whether the sample cloud starts matching the bright regions of the target heatmap or drifts into a biased pattern. This is the heart of “from chain to target.” The target distribution acts like a specification, and the chain is your mechanism for approximating it through time. If the mechanism is well designed, empirical frequencies become useful estimates for probabilities, expectations, and uncertainty. You can connect this back to <ref slide="1">Why Sampling Beats Solving</ref>: rather than normalizing the whole distribution exactly, you exploit long-run visitation. The next step is to understand a standard rule for deciding whether a proposed move should be accepted so that the chain preserves the target. That rule appears in <ref slide="4">Metropolis Acceptance Rule</ref>. ## Metropolis Acceptance Rule The **Metropolis algorithm** gives a simple way to turn local proposals into samples from a target distribution. Starting at the current state, you propose a candidate nearby. If the candidate has higher target probability, you usually accept it. If it has lower probability, you may still accept it with some probability rather than always rejecting it. That occasional downhill move is essential. Without it, the chain would behave too much like optimization and get trapped near a local peak. The **acceptance probability** balances exploration and preference for high-probability regions. For a symmetric proposal, the rule is based on the ratio of target probabilities, often written as `min(1, p(new)/p(old))`. <viz id="3"></viz> **Change the proposal step size** and **click to generate proposals**. **Notice which moves are always accepted, sometimes accepted, or rejected**. Then **watch the acceptance-rate meter** as you make proposals larger or smaller. This rule is one reason MCMC is so powerful: it only needs relative probabilities, not the full normalized distribution. If two states have scores proportional to their plausibility, their ratio is enough for the accept/reject decision. You can think of it like a probabilistic gate in a search loop. Greedy search accepts only improvements; Metropolis accepts all improvements and some degradations, which prevents the sampler from collapsing into pure hill climbing. But there is a catch: even with a correct rule, the chain can still move too slowly through the space. That practical issue is the subject of <ref slide="5">Why Mixing Is Hard</ref>. ## Why Mixing Is Hard A chain can be correct in theory and still frustrating in practice. **Mixing** refers to how quickly the sampler explores the target distribution well enough that its samples look representative of the long-run behavior. When the distribution has separated modes, narrow bridges, or awkward geometry, the chain may spend a long time stuck in one region before finding another. This creates highly correlated samples. If successive draws are very similar, then a thousand iterations may contain far less than a thousand independent pieces of information. That is why MCMC performance is often discussed in terms of **effective sample size (ESS)** and **autocorrelation**, not just raw iteration count. <viz id="4"></viz> **Increase and decrease the proposal step size** while watching whether the walker can reach both modes. **Change the barrier height** and **compare the trace plot with the diagnostics** to see when long runs in one region create strong autocorrelation and low effective sample size. This is where theory meets engineering. A sampler may have the right stationary distribution, but if it takes too long to move between important regions, your finite run gives a distorted picture. In modern ML terms, the issue is not just asymptotic correctness; it is throughput of useful information. A useful analogy is cache behavior in a large system: cheap local steps can still perform badly if they keep revisiting the same neighborhood. The next question is where this tradeoff actually matters in AI workflows, which you will see in <ref slide="6">Where AI Uses MCMC</ref>. # Where AI Uses MCMC A single best weight set gives one prediction but says nothing about confidence. Bayesian AI instead keeps the **posterior** — the full distribution of plausible weights given the data — and MCMC turns that distribution into usable **samples**. Average the samples for a forecast; spread them for an uncertainty band. ### Pipeline `params + data -> posterior -> MCMC samples -> predictions + uncertainty` ### Where it shows up - **Bayesian neural nets** — sample weights to quantify deep-learning doubt. - **Topic models** — sample document-topic mixtures to cluster text. - **Graphical models** — sample latent variables behind genetics, vision, etc. ### The three-way trade (accuracy vs uncertainty vs compute) | Method | Uncertainty | Speed | |---|---|---| | MCMC | faithful, exact-ish | slow | | Variational inference | biased, approximate | fast | | Gradient optimization | none (one point) | fastest | The tempting wrong guess is that variational inference loses the most information — it is the "approximate" one. But gradient optimization is worse: it keeps a single point and therefore has **zero** uncertainty. MCMC is the gold standard for honest uncertainty; you pay for it in compute (see <ref slide="7">Compute Cost And Tradeoffs</ref>), and whether MCMC even mixes well depends on <ref slide="5">Why Mixing Is Hard</ref>. # Compute Cost & Tradeoffs MCMC iterations are cheap; independent answers are not. The real budget is **cost per effective sample**, not cost per iteration. ## The three dials you control - **Dimension** — how many coordinates the chain explores. - **Proposal quality** — how well each guess targets the next point. - **Number of modes** — how many separated peaks the target hides. ## The three symptoms they push up - convergence slows - autocorrelation climbs - compute budget blows up ## Modern analogies - High dimension → **cache misses**: proposals keep missing the real mass. - Bad proposal → **local search** stuck in a valley, shuffling in place. - Many modes → a **cheap biased estimator** vs the expensive ground truth of visiting every peak. ## The trap People count iterations and assume cost scales linearly with dimension. It does not. Effective sample size `ESS = N / (1 + 2 * sum rho_t)` shrinks as autocorrelation `rho_t` climbs, and autocorrelation explodes with dimension — so doubling dimension can multiply cost per real answer by 10x or more. ## Rule Measure ESS before trusting a chain. Tune the dials to maximize independent answers per dollar, not raw iterations. <ref slide="8">Tune The Sampler</ref> shows the knobs. ## Tune The Sampler A Metropolis sampler that *runs* is not a sampler that *works*. The practical art of MCMC is **tuning** — choosing the proposal step size, the run length, and the burn-in so the chain actually represents the distribution you care about, without wasting compute (<ref slide="7">Compute Cost And Tradeoffs</ref>). Here the target is hidden. It has **two modes** separated by a low-density valley, but you cannot see its curve — you only see two things: the **accumulating sample histogram** (where the chain actually landed) and the **trace plot** (the chain's value over time). From these you must infer the shape and judge whether you are sampling it well. Three objectives must be met **simultaneously**: - **Reach both modes** — the histogram must fill mass on *both* the left and the right. A chain that crawls never escapes its starting mode. - **Healthy acceptance** — between roughly 20 % and 50 %. Too high means your steps are tiny and you barely move; too low means you are stuck rejecting everything. (See <ref slide="4">Metropolis Acceptance Rule</ref>.) - **Effective sample size (ESS) ≥ 200** — your usable independent information after autocorrelation is accounted for. A sticky, highly correlated chain can run thousands of steps yet yield a handful of effective samples (<ref slide="5">Why Mixing Is Hard</ref>). The tension is the whole point. A **small step** raises acceptance but leaves a sticky, autocorrelated chain that never crosses the valley — fails modes and ESS. A **huge step** crashes acceptance — fails acceptance and freezes the chain. And under the fixed **1500-iteration budget**, every sample dumped into burn-in is one fewer contributing to ESS, so burn-in must be *enough but not lavish*. <viz id="1"></viz> **Adjust the three controls** and watch the diagnostics update instantly: - **Step size σ** — sweep it and feel the tradeoff: acceptance falls while mode-crossing rises. The sweet spot is a compromise, never an extreme. - **Iterations** — spends your compute budget. More samples raise ESS, capped at 1500. - **Burn-in** — discards the initial transient. Too little and a one-sided start pollutes the histogram; too much and you waste budget you needed for ESS. Read the three objective meters on the right: each turns teal only when its target is met. The **trace** is your forensic tool — flat plateaus are rejected proposals, long runs at one level mean the chain is trapped, and zig-zags across the centre mean it is crossing modes. **Solve the challenge by getting all three meters green at the same time.**