Stein's method for normal approximation
/ stine /
Stein's method for normal approximation is a remarkably general technique, introduced by Charles Stein in 1972, for bounding the distance between the distribution of a random variable and the standard normal — crucially, with explicit error bounds and WITHOUT requiring independence, where the classical characteristic-function proof of the central limit theorem breaks down. The CLT says a normalised sum of many weakly-dependent variables is approximately Gaussian, but classical Fourier methods need independence and give only the limit, not a rate. Stein's method handles dependent summands (local dependence, exchangeable pairs, size-biasing) and produces quantitative bounds, including Berry-Esseen-type rates, making it indispensable in modern probabilistic combinatorics and high-dimensional statistics.
The starting point is Stein's characterisation: a random variable Z is standard normal N(0,1) if and only if E[f'(Z) - Z f(Z)] = 0 for all suitably smooth bounded f. To bound how far a variable W is from normal, choose a test function h and solve the Stein equation f'(x) - x f(x) = h(x) - E[h(N)] for f; then the quantity E[h(W)] - E[h(N)] equals E[f'(W) - W f(W)], so bounding the distance reduces to bounding this single expectation using the structure of W. Several couplings make E[f'(W) - W f(W)] tractable: the exchangeable-pair approach constructs a pair (W, W') with the same marginal distribution that differ by a small step and satisfy a linearity-of-regression condition E[W' - W given W] = -lambda W; the size-bias and zero-bias couplings give other routes. Each turns the abstract expectation into a concrete sum of small, controllable error terms, yielding a bound on a probability metric (Wasserstein, Kolmogorov, or total variation distance) to the normal.
Its importance is that it is the method of choice for central limit theorems with dependence and with explicit rates: counts of subgraphs and patterns, statistics on random permutations (the number of descents, the longest increasing subsequence's fluctuations in some regimes), antivoter and other interacting models, and many statistical estimators all yield to it where Fourier methods fail. It also extends to multivariate and even functional (Stein-Malliavin) normal approximation on Gaussian spaces. The honest caveat is that solving and bounding the Stein equation requires regularity of the solution f (one needs bounds on f, f', and sometimes f'') and a good coupling; constructing the right exchangeable pair or size-bias coupling is an art, and a poor coupling gives a weak or vacuous bound. The method gives an upper bound on a distance, not the exact limiting law — and a small Wasserstein distance does not automatically translate into a small Kolmogorov (cdf) distance without extra smoothing arguments.
Number of fixed points / a sum over a dependent structure. Take W = (number of edges of a fixed graph H present in G(n,p), centred and scaled). The summands (edge indicators contributing to H-copies) are locally dependent. Build an exchangeable pair by resampling one random edge; verify E[W' - W given W] = -lambda W approximately, and Stein's method yields a Wasserstein bound of order, say, 1/sqrt(number of copies), giving a quantitative CLT for the subgraph count where the characteristic-function proof cannot cope with the dependence.
Stein identity E[f'(Z) - Z f(Z)] = 0 + a coupling turns 'how normal is W?' into a bounded error sum.
Constructing the right exchangeable-pair or size-bias coupling is an art — a poor coupling gives a vacuous bound — and a small Wasserstein bound does not automatically give a small Kolmogorov (cdf) distance without extra smoothing.