A joint distribution over $n$ binary variables needs $2^n-1$ numbers; at 30 variables that already exceeds a billion. But the world is never fully connected. Draw direct dependencies as arrows, and the real information lives in the edges you did not draw—every missing edge asserts a conditional independence, and the joint collapses from exponential into a product of small tables.
Stranger still is explaining away. Wet grass may be caused by rain or by the sprinkler; the two causes start out unrelated. Yet once you see that the grass is wet, learning that it rained last night immediately lowers your belief that the sprinkler ran—the rain has already accounted for the wetness. Observing a common effect makes its two causes dependent out of thin air.
$\mathrm{pa}(X_i)$ is the set of parents of $X_i$ in the directed acyclic graph. The line says one thing: given its direct causes, a variable is independent of all its non-descendants. Storage drops from $2^n$ to $\sum_i 2^{|\mathrm{pa}(X_i)|}$. The graph is not an illustration of the distribution—the graph is half its definition; the other half is just the local conditional probability tables.
There is a dictionary here between graph theory and probability. d-separation is a purely combinatorial test: trace the paths, note which nodes are observed, touch no integral. Its conclusion, however, is about the distribution—separation in the graph implies conditional independence in the distribution, and for almost all parameter values the converse holds too. A question you can answer by running a finger along arrows is equivalent to whether a family of high-dimensional integrals coincide. This syntax–semantics correspondence is not an isolated case (Day 19, Day 47): mathematics rewards, again and again, those who demote a semantic question to a syntactic one.
The QMR-DT diagnostic system links hundreds of diseases to thousands of symptoms through a two-layer network; genetic linkage analysis propagates genotype beliefs along pedigree graphs. The deepest step was Pearl's promotion of arrows from dependence to causation: with the intervention operator $do(x)$, the graph can decide whether a causal effect is identifiable from purely observational data (the back-door criterion)—"correlation is not causation" became a computable proposition.
The Markov property is a single sentence: the future depends on the past only through the present. The current state is a sufficient statistic for the entire history—remember it and you can throw the logs away.
Picture a crowd doing a random walk on a state graph, each person stepping by the same rule. However strange the starting distribution, after enough steps the crowd's overall distribution stops changing—inflow into each state exactly balances outflow. Individuals still jump about; the macroscopic shape has frozen.
$P$ is the transition matrix, $P_{ij}$ the probability of jumping from $i$ to $j$; the row vector $\pi$ is a distribution over states. The equation says $\pi$ is the left eigenvector of $P$ for eigenvalue 1—one step leaves the distribution untouched. If the chain is irreducible and aperiodic, $\pi$ is unique; error decays like $|\lambda_2|^t$, so the larger the spectral gap, the faster the mixing (Day 4, Day 48).
The rule is entirely local—each state knows only where it jumps—yet the result is global and unique, and it is the most basic object in linear algebra: an eigenvector. PageRank is exactly this sentence cashed out: "an important page is one linked to by important pages" is a circular definition, and the eigenvector equation unwinds it.
Lovelier still is running the logic backwards: instead of taking a chain and finding its stationary distribution, take the distribution you want to sample and design a chain that has it as its stationary distribution. Detailed balance $\pi_i P_{ij}=\pi_j P_{ji}$ involves only ratios of $\pi$, so the intractable normalizing constant cancels—which is precisely why high-dimensional posteriors you cannot write down can still be sampled from.
PageRank and the random walks behind recommender systems; MCMC, which underpins modern Bayesian statistics and Ising-model simulation; queueing theory, where the stationary distribution gives waiting times. Shannon modelled English letter sequences as a Markov chain—the prehistory of language models (Day 13). The newest instance is diffusion models: the forward noising process is a Markov chain that grinds data into Gaussian noise, and the network learns its time reversal.
The real state evolves backstage as a Markov chain—the phoneme a speaker intends, a bull or bear regime, whether a stretch of genome is coding or not. You see only what it randomly "renders": a waveform, a day's return, a base pair. The chain walks in the dark; you guess from the light.
The difficulty: a length-$T$ observation admits $|S|^T$ hidden paths that all explain it. What saves you is the Markov property—two paths with different histories that sit in the same state right now have identical influence on the future, so they can be merged on the spot into a single number.
Two parameter sets: transitions $A_{ij}=P(z_t=j\mid z_{t-1}=i)$ and emissions $B_{jk}=P(x_t=k\mid z_t=j)$. The forward recursion is
Read $\alpha_t(j)$ as the joint probability of "having produced every observation $x_{1:t}$ so far, and sitting in state $j$ right now". The sum inside the bracket is the whole secret: it merges every history leading into $j$ into one number, because the future depends on $j$ and not on how you reached $j$. Outside the bracket, the emission term absorbs the current observation's evidence. Cost falls from $O(|S|^T)$ to $O(|S|^2T)$.
On the same trellis, replace $\sum$ with $\max$ and you no longer compute a marginal but the single most likely hidden path—that is Viterbi. The two algorithms looking identical is no coincidence: they are the same recursion instantiated over different semirings, with $(+,\times)$ giving a sum of probabilities and $(\max,\times)$ giving an optimal path. The skeleton of an algorithm has been cleanly separated from the algebra it computes over: change the semiring and you change the meaning; shortest paths and sequence alignment sit in the same table. You thought you were solving one problem and proved a whole family (Day 19).
Speech recognition was ruled by HMMs for thirty years before deep learning: hidden states were phonemes, emissions modelled acoustics. Bioinformatics uses them for gene prediction and sequence alignment; Viterbi decoding runs in the convolutional-code decoder of nearly every mobile phone (Day 33). Even today, the CTC loss in end-to-end speech models runs the same forward–backward recursion—only the emission probabilities now come from a neural network.
The first three concepts are special cases of one algorithm. Read the graph as a communication network: each node knows only its relationships to its neighbours, summarizes "here is what I think you should look like" into a message, and updates its own belief once its neighbours have replied. Run this protocol once on a tree and every node ends up holding exactly the correct marginal—yet global inference was never executed as a whole by any node. It emerges out of local conversation. This is the worldview of distributed systems: no central coordinator, global consistency guaranteed by a local protocol.
$\phi_i$ is node $i$'s own evidence, $\psi_{ij}$ the edge compatibility (how plausible this pair of values is), and $N(i)\setminus j$ the neighbours other than $j$—what $j$ just told you must not be handed back to $j$, or belief reinforces itself into an echo chamber. The sum marginalizes out $i$'s possibilities, leaving only its opinion about $j$.
Once the graph has cycles the protocol loses its guarantees, yet people run it anyway (loopy BP) and it often works absurdly well; only a decade later did it become clear that it optimizes the Bethe free energy from statistical physics. The same equation was discovered independently in three unrelated fields: the cavity method in statistical physics, LDPC decoding in coding theory, and belief propagation in AI.
When exact inference really is out of reach there is a second road: turn inference into optimization—search a family of simple distributions $q$ for the one closest to the true posterior by maximizing the lower bound
The first term pushes $q$ onto high-probability regions; the second is $q$'s entropy, stopping it from collapsing to a point. The gap between the bound and $\log P(x)$ is exactly a KL divergence. "Compute an integral" has become "run gradient descent"—which is precisely the VAE objective.
LDPC and turbo codes decode with loopy BP and push rates close to the Shannon limit (Day 13, Day 33). The training objectives of VAEs and diffusion models are both variants of the ELBO. Every layer of a graph neural network is a learnable version of message passing—the hand-designed potentials replaced by neural networks; attention, too, can be read as one round of message passing on a fully connected graph. Deep learning did not abolish graphical models, it parameterized their inference step.