the Stein-Chen method
/ stine chen /
The Stein-Chen method is a technique for bounding how close the distribution of a sum of dependent indicator variables is to a Poisson distribution, with an explicit, computable error bound — not merely an asymptotic limit. The classical Poisson limit theorem says a sum of many rare independent events is approximately Poisson, but it is a limit statement and assumes independence. In combinatorics one constantly meets sums of dependent rare indicators (the number of isolated vertices, the number of fixed points of a random permutation, the number of occurrences of a small subgraph), and one wants not just 'approximately Poisson' but a quantitative bound on the error that survives dependence. The Stein-Chen method delivers exactly this.
The idea, due to Charles Stein and adapted to the Poisson case by Louis Chen, is a characterisation rather than a limit. A random variable Z is Poisson with mean lambda if and only if E[lambda f(Z+1) - Z f(Z)] = 0 for all bounded f — this is Stein's identity for the Poisson. To measure how far the law of a count W = sum of indicators X_i is from Poisson(lambda) with lambda = E[W], one solves the Stein equation lambda f(k+1) - k f(k) = g(k) - Poisson-expectation of g for a test function g, then bounds E[lambda f(W+1) - W f(W)] using the dependence structure of the X_i. The headline theorem, in the locally-dependent case, gives a total variation bound of the form: distance(law of W, Poisson(lambda)) <= (b_1 + b_2)(1 - e^(-lambda))/lambda, where b_1 = sum over i, j in the dependency neighbourhood of E[X_i] E[X_j] measures the 'self' dependence and b_2 = sum of E[X_i X_j] over overlapping pairs measures the covariance, both built from a chosen neighbourhood of dependence for each index.
Its importance is that it makes Poisson approximation a quantitative, dependence-tolerant tool: you get an explicit number bounding the error in total variation, valid for finite n, even when the indicators are positively or negatively associated. This is exactly what is needed in the probabilistic study of discrete structures — proving, say, that the number of triangles in a sparse random graph is approximately Poisson with a controlled error, which then immediately gives the limiting probability of triangle-freeness as e^(-lambda). The honest caveat is that the quality of the bound is only as good as the dependency neighbourhoods you can construct: the method requires identifying, for each X_i, a set of indices on which it strongly depends and arguing the rest are nearly independent; when dependence is global or long-range the bounds b_1, b_2 do not become small and the method gives nothing useful. Total-variation closeness to Poisson also does not by itself certify a normal limit — that is the regime of Stein's method for normal approximation.
Number of isolated vertices in G(n, p) with p = (log n + c)/n. Let W count isolated vertices; W = sum of X_i where X_i indicates vertex i has no neighbour, P(X_i = 1) = (1-p)^(n-1), so lambda = E[W] -> e^(-c). Vertex i's indicator depends mainly on the (few) other vertices via shared potential edges; the Stein-Chen bound on b_1 + b_2 is O(1/n), so the total-variation distance from Poisson(e^(-c)) is O(1/n). Hence P(no isolated vertex) -> exp(-e^(-c)), the classical connectivity-threshold limit, now with an explicit error rate.
An explicit total-variation bound to Poisson(lambda) that survives dependence: distance <= (b_1+b_2)(1-e^(-lambda))/lambda.
The bound is only as good as the dependency neighbourhoods you can build: when each X_i depends strongly on only a few others it is excellent, but global or long-range dependence leaves b_1, b_2 large and the method gives nothing.