Stein's method is a general method in probability theory to obtain bounds on the distance between two probability distributions with respect to a probability metric. It was introduced by Charles Stein, who first published it in 1972, to obtain a bound between the distribution of a sum of m {\displaystyle m} -dependent sequence of random variables and a standard normal distribution in the Kolmogorov (uniform) metric and hence to prove not only a central limit theorem, but also bounds on the rates of convergence for the given metric.
History At the end of the 1960s, unsatisfied with the by-then known proofs of a specific central limit theorem, Charles Stein developed a new way of proving the theorem for his statistics lecture. His seminal paper was presented in 1970 at the sixth Berkeley Symposium and published in the corresponding proceedings. Later, his Ph.D. student Louis Chen Hsiao Yun modified the method so as to obtain approximation results for the Poisson distribution; therefore the Stein method applied to the problem of Poisson approximation is often referred to as the Stein–Chen method. Probably the most important contributions are the monograph by Stein (1986), where he presents his view of the method and the concept of auxiliary randomisation, in particular using exchangeable pairs, and the articles by Barbour (1988) and Götze (1991), who introduced the so-called generator interpretation, which made it possible to easily adapt the method to many other probability distributions. An important contribution was also an article by Bolthausen (1984) on the so-called combinatorial central limit theorem. In the 1990s the method was adapted to a variety of distributions, such as Gaussian processes by Barbour (1990), the binomial distribution by Ehm (1991), Poisson processes by Barbour and Brown (1992), the Gamma distribution by Luk (1994), and many others. A class of approximations available via Stein's method can be found in Novak S.Y. (2011), ch. 12. The method gained further popularity in the machine learning community in the mid 2010s, following the development of computable Stein discrepancies and the diverse applications and algorithms based on them.
The basic approach
Probability metrics Stein's method is a way to bound the distance between two probability distributions using a specific probability metric. Let the metric be given in the form
( 1.1 ) d ( P , Q ) = sup h ∈ H | ∫ h d P − ∫ h d Q | = sup h ∈ H | E [ h ( W ) ] − E [ h ( Y ) ] | {\displaystyle (1.1)\quad d(P,Q)=\sup _{h\in {\mathcal {H}}}\left|\int h\,dP-\int h\,dQ\right|=\sup _{h\in {\mathcal {H}}}{\Bigl |}E[h(W)]-E[h(Y)]{\Bigr |}}
Here, P {\displaystyle P} and Q {\displaystyle Q} are probability measures on a measurable space X {\displaystyle {\mathcal {X}}} , W {\displaystyle W} and Y {\displaystyle Y} are random variables with distribution P {\displaystyle P} and Q {\displaystyle Q} respectively, E {\displaystyle E} is the usual expectation operator and H {\displaystyle {\mathcal {H}}} is a set of functions from X {\displaystyle {\mathcal {X}}} to the set of real numbers. Set H {\displaystyle {\mathcal {H}}} has to be large enough, so that the above definition indeed yields a metric. Important examples are the total variation metric, where we let H {\displaystyle {\mathcal {H}}} consist of all the indicator functions of measurable sets, the Uniform (Kolmogorov's) metric for probability measures on the real numbers, where we consider all the half-line indicator functions, and the Gini-Kantorovich (Wasserstein) metric, where one deals with the set H {\displaystyle {\mathcal {H}}} of all Lipschitz-continuous functions with Lipschitz constant 1. However, note that not every metric can be represented in the form (1.1). In what follows P {\displaystyle P} is a complicated distribution (e.g., the distribution of a sum of dependent random variables), which we want to approximate by a much simpler and tractable distribution Q {\displaystyle Q} (e.g., the standard normal distribution or the Poisson distribution).
… excerpt ends here. Continue reading the full article.
