Blog · Collection
Probabilistic models and Monte Carlo
Simulation and importance sampling, mixture models and EM, Markov chains, hidden Markov models, MCMC and the Kalman filter.
Probability models are only as useful as the computational methods that make them usable, so this overview pairs the two.
Simulation and Monte Carlo integration
It starts with generating random numbers: inverse-CDF transforms, rejection sampling and other ways of turning uniform draws into draws from the distribution you want. Monte Carlo integration then approximates an expectation with an average,
with an error that shrinks like whatever the dimension. Importance sampling draws from a convenient distribution instead and reweights each draw by . It only works well when has heavier tails than ; otherwise a few enormous weights dominate the estimate.
Latent variables and EM
Gaussian mixture models attach a hidden cluster label to each observation. The EM algorithm alternates between computing the expected labels under the current parameters (the E-step) and refitting the parameters as if those labels had been observed (the M-step). No iteration can decrease the likelihood, which makes EM a dependable workhorse, although it can stop at a local maximum. The multivariate normal and Wishart distributions supply the pieces these models are built from.
Markov chains and hidden Markov models
Discrete Markov chains bring transition matrices, stationary distributions and first-step analysis, which computes hitting times and absorption probabilities by conditioning on the first move. A hidden Markov model puts a Markov chain behind noisy observations. The forward–backward recursions compute the probability of each hidden state in time linear in the length of the sequence, and the Viterbi algorithm finds the single most likely path. For continuous states with linear Gaussian dynamics, the Kalman filter does the same job in closed form.
Markov chain Monte Carlo
When direct sampling is impossible, MCMC builds a Markov chain whose stationary distribution is the target. The Metropolis–Hastings rule and the Gibbs sampler are the two basic constructions. Convergence theory for general state spaces, built on irreducibility, aperiodicity and conditions under which the chain forgets where it started, explains why the averages converge. Autoregressive processes give a simple setting in which the speed of mixing can be computed exactly. Several of these samplers are in the MCMC playground.