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,

Ep[h(X)]≈1N∑i=1Nh(Xi),Xi∼p,\mathbb{E}_p[h(X)] \approx \frac{1}{N}\sum_{i=1}^{N} h(X_i), \qquad X_i \sim p,

with an error that shrinks like N−1/2N^{-1/2} whatever the dimension. Importance sampling draws from a convenient distribution qq instead and reweights each draw by p(Xi)/q(Xi)p(X_i)/q(X_i). It only works well when qq has heavier tails than pp; 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.

← All collections