View source for Stein's method

{{confuse|Stein's lemma}}
'''Stein's method''' is a general method in [[Probability theory|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,<ref name="stein1972">
{{Cite book
 | year=1972
 | chapter=A bound for the error in the normal approximation to the distribution of a sum of dependent random variables
 | chapter-url=http://projecteuclid.org/euclid.bsmsp/1200514239
 | title=Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 2
 |volume=6 |issue=2 | publisher=University of California Press
 | pages=583–602
 | mr=402873
 | zbl=0278.60026
}}</ref> to obtain a bound between the distribution of a sum of <math>m</math>-dependent sequence of random variables and a [[Normal distribution|standard normal distribution]] in the [[Uniform norm|Kolmogorov (uniform) metric]] and hence to prove not only a [[Central limit theorem|central limit theorem]], but also bounds on the rates of [[Limit of a sequence|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|central limit theorem]], Charles Stein developed a new way of proving the theorem for his [[Statistics|statistics]] lecture.<ref>[http://www.ims.nus.edu.sg/imprints/interviews/CharlesStein.pdf Charles Stein: The Invariant, the Direct and the "Pretentious"] {{Webarchive|url=https://web.archive.org/web/20070705012113/http://www.ims.nus.edu.sg/imprints/interviews/CharlesStein.pdf |date=2007-07-05 }}. Interview given in 2003 in Singapore</ref> His seminal paper was presented in 1970 at the sixth Berkeley Symposium and published in the corresponding proceedings.<ref name="stein1972"/>

Later, his [[Ph.D.]] student Louis Chen Hsiao Yun modified the method so as to obtain approximation results for the [[Poisson distribution]];<ref name="chen1975">
{{cite journal
 |year=1975
 |title=Poisson approximation for dependent trials
 |journal=Annals of Probability
 |volume=3 |issue=3 |pages=534–545
 |doi=10.1214/aop/1176996359
 |jstor=2959474
 |mr=428387
 |zbl=0335.60016
|doi-access=free
 }}</ref> 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''.{{Citation needed|date=August 2010}}

In the 1990s the method was adapted to a variety of distributions, such as [[Gaussian process]]es by Barbour (1990), the [[Binomial distribution|binomial distribution]] by Ehm (1991), Poisson processes by Barbour and Brown (1992), the [[Gamma distribution]] by Luk (1994), and many others.

The method gained further popularity in the machine learning community in the mid 2010s, following the development of [[Stein discrepancy|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 
:<math>
   (1.1)\quad 
   d(P,Q) 
   = \sup_{h\in\mathcal{H}}\left|\int h \, dP - \int h \, dQ \right|
   = \sup_{h\in\mathcal{H}}\left|E h(W) - E h(Y) \right|

</math>
Here, <math>P</math> and <math>Q</math> are probability measures on a [[Measurable space|measurable space]] <math>\mathcal{X}</math>, <math>W</math> and <math>Y</math> are random variables with distribution <math>P</math> and <math>Q</math> respectively, <math>E</math> is the usual expectation operator and <math>\mathcal{H}</math> is a set of functions from <math>\mathcal{X}</math> to the set of real numbers. Set <math>\mathcal{H}</math> has to be large enough, so that the above definition indeed yields a [[Metric (mathematics)|metric]].

Important examples are the [[Total variation distance of probability measures|total variation metric]], where we let <math>\mathcal{H}</math> consist of all the [[Indicator function|indicator function]]s of measurable sets, the [[Uniform norm|Kolmogorov (uniform) metric]] for probability measures on the real numbers, where we consider all the half-line indicator functions, and the [[Wasserstein metric|Lipschitz (first order Wasserstein; Kantorovich) metric]], where the underlying space is itself a metric space and we take the set <math>\mathcal{H}</math> to be all [[Lipschitz continuity|Lipschitz-continuous]] functions with Lipschitz-constant 1. However, note that not every metric can be represented in the form (1.1).

In what follows <math>P</math> 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 <math>Q</math> (e.g.,  the standard normal distribution).

===The Stein operator===

We assume now that the distribution <math>Q</math> is a fixed distribution; in what follows we shall in particular consider the case where <math>Q</math> is the standard normal distribution, which serves as a classical example.

First of all, we need an operator <math>\mathcal{A}</math>, which acts on functions <math>f</math> from <math>\mathcal{X}</math> to the set of real numbers and 'characterizes' distribution  <math>Q</math>  in the sense that the following equivalence holds: 
:<math>
 (2.1)\quad
 E ((\mathcal{A}f)(Y)) = 0\text{ for all } f  \quad \iff \quad Y \text{ has distribution } Q.
</math>
We call such an operator the ''Stein operator''.

For the standard normal distribution, [[Stein's lemma]] yields such an operator:
:<math>
 (2.2)\quad
 E\left(f'(Y)-Yf(Y)\right) = 0\text{ for all } f\in C_b^1  \quad \iff \quad Y \text{ has standard normal distribution.}
</math>
Thus, we can take
:<math>
 (2.3)\quad
(\mathcal{A}f)(x) = f'(x) - x f(x).
</math>
There are in general infinitely many such operators and it still remains an open question, which one to choose. However, it seems that for many distributions there is a particular ''good'' one, like (2.3) for the normal distribution.

There are different ways to find Stein operators.<ref name=Novak>
{{cite book
 |last=Novak |first=S.Y.
 |year=2011
 |title=Extreme Value Methods with Applications to Finance
 |at=Ch. 12
 |series=Monographs on Statistics and Applied Probability
 |volume=122
 |publisher=CRC Press
 |isbn=978-1-43983-574-6
}}</ref>

===The Stein equation===

<math>P</math> is close to <math>Q</math> with respect to <math>d</math> if the difference of expectations in (1.1) is close to 0. We hope now that the operator <math>\mathcal{A}</math> exhibits the same behavior: if <math>P=Q</math> then <math>E (\mathcal{A}f)(W)=0</math>, and hopefully if <math>P\approx Q</math> we have <math>E (\mathcal{A}f)(W) \approx 0</math>.

It is usually possible to define a function <math>f = f_h</math> such that 
:<math> (3.1)\quad 
(\mathcal{A}f)(x)= h(x) - E[h(Y)] \qquad\text{ for all } x .
</math>
We call (3.1) the ''Stein equation''. Replacing <math>x</math> by <math>W</math> and taking expectation with respect to <math>W</math>, we get 
:<math> (3.2)\quad
E(\mathcal{A}f)(W)=E[h(W)] - E[h(Y)].
</math>
Now all the effort is worthwhile only if the left-hand side of (3.2) is easier to bound than the right hand side. This is, surprisingly, often the case.

If <math>Q</math> is the standard normal distribution and we use (2.3), then the corresponding Stein equation is
:<math> (3.3)\quad
f'(x) - x f(x) = h(x) - E[h(Y)] \qquad\text{for all }x . 
</math>

If probability distribution Q has an absolutely continuous (with respect to the Lebesgue measure) density q, then<ref name=Novak/>
:<math> (3.4)\quad 
  (\mathcal{A}f)(x) = f'(x)+f(x)q'(x)/q(x).
</math>

===Solving the Stein equation===

''Analytic methods''. Equation (3.3) can be easily solved explicitly:
:<math> (4.1)\quad
f(x) = e^{x^2/2}\int_{-\infty}^x [h(s)-E h(Y)]e^{-s^2/2} \, ds.
</math>

''Generator method''. If <math>\mathcal{A}</math> is the generator of a Markov process <math>(Z_t)_{t\geq 0}</math> (see Barbour (1988), Götze (1991)), then the solution to (3.2) is
:<math>
(4.2)\quad
f(x) = -\int_0^\infty [E^x h(Z_t)-E h(Y)] \, dt,
</math>
where <math>E^x</math> denotes expectation with respect to the process <math>Z</math> being started in <math>x</math>. However, one still has to prove that the solution (4.2) exists for all desired functions <math>h\in\mathcal{H}</math>.

===Properties of the solution to the Stein equation===

Usually, one tries to give bounds on <math>f</math> and its derivatives (or differences) in terms of <math>h</math> and its derivatives (or differences), that is, inequalities of the form
:<math>
(5.1)\quad
\|D^k f\| \leq C_{k,l} \|D^l h\|, 
</math>
for some specific <math>k,l=0,1,2,\dots</math> (typically <math>k\geq l</math> or <math>k\geq l-1</math>, respectively, depending on the form of the Stein operator), where often <math>\|\cdot\|</math> is the supremum norm. Here, <math>D^k</math> denotes the [[Differential operator|differential operator]], but in discrete settings it usually refers to a difference operator. The constants <math>C_{k,l}</math> may contain the parameters of the distribution <math>Q</math>. If there are any, they are often referred to as ''Stein factors''.

In the case of (4.1) one can prove for the supremum norm that
:<math>
(5.2)\quad
\|f\|_\infty\leq \min\left\{\sqrt{\pi/2}\|h\|_\infty,2\|h'\|_\infty\right\},\quad
\|f'\|_\infty\leq \min\{2\|h\|_\infty,4\|h'\|_\infty\},\quad
\|f''\|_\infty\leq 2 \|h'\|_\infty,
</math>
where the last bound is of course only applicable if <math>h</math> is differentiable (or at least Lipschitz-continuous, which, for example, is not the case if we regard the total variation metric or the Kolmogorov metric!). As the standard normal distribution has no extra parameters, in this specific case the constants are free of additional parameters.

If we have bounds in the general form (5.1), we usually are able to treat many probability metrics together. One can often start with the next step below, if bounds of the form (5.1) are already available (which is the case for many distributions).

===An abstract approximation theorem===

We are now in a position to bound the left hand side of (3.1). As this step heavily depends on the form of the Stein operator, we directly regard the case of the standard normal distribution.

At this point we could directly plug in random variable <math>W</math>, which we want to approximate, and try to find upper bounds. However, it is often fruitful to formulate a more general theorem. Consider here the case of local dependence.

Assume that <math> W=\sum_{i=1}^n X_i </math> is a sum of random variables such that the <math>E[W] = 0</math> and [[Variance|variance]] <math>\operatorname{var}[W] = 1</math>. Assume that, for every <math>i=1,\dots,n</math>, there is a set <math>A_i\subset\{1,2,\dots,n\}</math>, such that <math>X_i</math> is independent of all the random variables <math>X_j</math> with <math>j\not\in A_i</math>. We call this set the 'neighborhood' of <math>X_i</math>. Likewise let <math>B_i\subset\{1,2,\dots,n\}</math> be a set such that all <math>X_j</math> with <math>j\in A_i</math> are independent of all <math>X_k</math>, <math>k\not\in B_i</math>. We can think of  <math>B_i</math> as the neighbors in the neighborhood of <math>X_i</math>, a second-order neighborhood, so to speak. For a set <math>A\subset\{1,2,\dots,n\}</math> define now the sum <math>X_A := \sum_{j\in A} X_j</math>.

Using Taylor expansion, it is possible to prove that
:<math>
(6.1)\quad
\left|E(f'(W)-Wf(W))\right| 
\leq \|f''\|_\infty\sum_{i=1}^n \left(
 \frac{1}{2}E|X_i X_{A_i}^2|
+ E|X_i X_{A_i}X_{B_i \setminus A_i}|
+ E|X_i X_{A_i}| E|X_{B_i}|
\right)
</math>

Note that, if we follow this line of argument, we can bound (1.1) only for functions where <math>\|h'\|_{\infty}</math> is bounded because of the third inequality of (5.2) (and in fact, if <math>h</math> has discontinuities, so will <math>f''</math>). To obtain a bound similar to (6.1) which contains only the expressions <math>\|f\|_\infty</math> and <math>\|f'\|_\infty</math>, the argument is much more involved and the result is not as simple as (6.1); however, it can be done.

'''Theorem A'''. If <math>W</math> is as described above, we have for the Lipschitz metric <math>d_W</math> that
:<math>
(6.2)\quad
d_W(\mathcal{L}(W),N(0,1)) \leq 2\sum_{i=1}^n \left(
 \frac{1}{2}E|X_i X_{A_i}^2|
+ E|X_i X_{A_i}X_{B_i \setminus A_i}|
+ E|X_i X_{A_i}| E|X_{B_i}|
\right).
</math>
'''Proof'''. Recall that the Lipschitz metric is of the form (1.1) where the functions <math>h</math> are Lipschitz-continuous with Lipschitz-constant 1, thus <math>\|h'\|\leq 1</math>. Combining this with (6.1) and the last bound in (5.2) proves the theorem.

Thus, roughly speaking, we have proved that, to calculate the Lipschitz-distance between a <math>W</math> with local dependence structure and a standard normal distribution, we only need to know the third moments of <math>X_i</math> and the size of the neighborhoods <math>A_i</math> and <math>B_i</math>.

===Application of the theorem===

We can treat the case of sums of [[Independent and identically distributed random variables|independent and identically distributed random variables]] with Theorem A.

Assume that <math>E X_i = 0</math>, <math> \operatorname{var} X_i = 1</math> and <math> W=n^{-1/2}\sum X_i </math>. We can take <math> A_i=B_i=\{i\} </math>. From Theorem A we obtain that
:<math>
(7.1)\quad
d_W(\mathcal{L}(W),N(0,1)) \leq \frac{5 E|X_1|^3}{n^{1/2}}.
</math>

For sums of random variables another approach related to Steins Method is known as the [[Zero bias transform|zero bias transform]].

==Connections to other methods==

*'''Lindeberg's device'''. [[Biography:Jarl Waldemar Lindeberg|Lindeberg]] (1922)  introduced a device, where the difference <math> E h(X_1+\cdots+X_n)-E h(Y_1+\cdots+Y_n) </math> is represented as a sum of step-by-step differences.

*'''Tikhomirov's method'''. Clearly the approach via (1.1) and (3.1) does not involve [[Characteristic function (probability theory)|characteristic functions]]. However, Tikhomirov (1980) presented a proof of a central limit theorem based on characteristic functions and a differential operator similar to (2.3). The basic observation is that the characteristic function <math>\psi(t)</math> of the standard normal distribution satisfies the differential equation <math>\psi'(t)+t\psi(t) = 0</math> for all <math>t</math>. Thus, if the characteristic function <math>\psi_W(t)</math> of <math>W</math> is such that <math>\psi'_W(t)+t\psi_W(t)\approx 0</math> we expect that <math>\psi_W(t)\approx \psi(t)</math> and hence that <math>W</math> is close to the normal distribution. Tikhomirov states in his paper that he was inspired by Stein's seminal paper.


==See also==
*[[Stein's lemma]]
*[[Stein discrepancy]]

==Notes==

{{Reflist}}

==References==

* {{Cite journal
| author = Barbour, A. D.
| title = Stein's method and Poisson process convergence
| year = 1988
| journal = Journal of Applied Probability
| volume = 25
| pages = 175–184
| doi = 10.2307/3214155
| jstor = 3214155
| s2cid = 121759039
}}
* {{Cite journal
|  author = Barbour, A. D.
|  title = Stein's method for diffusion approximations
|  journal = Probability Theory and Related Fields
|  year = 1990
|  volume = 84
|  issue = 3
|  pages = 297–322
|  doi = 10.1007/BF01197887
| s2cid = 123057547
|  doi-access = free
}}
* {{Cite journal
|author1=Barbour, A. D.  |author2=Brown, T. C.
 |name-list-style=amp |  title = Stein's method and point process approximation
|  journal = Stochastic Processes and Their Applications
|  year = 1992
|  volume = 43
|  issue = 1
|  pages = 9–31
|  doi = 10.1016/0304-4149(92)90073-Y
|  doi-access = free
}}
* {{Cite journal
| author = Bolthausen, E.
| title = An estimate of the remainder in a combinatorial central limit theorem
| journal = Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete
| volume = 66
| year = 1984
| issue = 3
| pages = 379–386
| doi = 10.1007/BF00533704
| s2cid = 121725342
| doi-access = free
}}
* {{Cite journal
|  author = Ehm, W.
|  title = Binomial approximation to the Poisson binomial distribution
|  journal = Statistics & Probability Letters
|  year = 1991
|  volume = 11
|  issue = 1
|  pages = 7–16
|  doi = 10.1016/0167-7152(91)90170-V
}}
* {{Cite journal
| author = Götze, F.
| title = On the rate of convergence in the multivariate CLT
| journal = The Annals of Probability
| volume = 19
| year = 1991
| issue = 2
| pages = 724–739
| doi = 10.1214/aop/1176990448
| doi-access = free
}}
* {{Cite journal
|  author = Lindeberg, J. W.
|  title = Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechung
|  journal = [[Mathematische Zeitschrift]]
|  year = 1922
|  volume = 15
|  issue = 1
|  pages = 211–225
|  doi = 10.1007/BF01494395
| s2cid = 119730242
| url = https://zenodo.org/record/2412242
}}
* {{Cite book
| author = Luk, H. M.
| title = Stein's method for the gamma distribution and related statistical applications
| year = 1994
| publisher = Dissertation
}}
* {{Cite book
| author = Novak, S. Y.
| title = Extreme value methods with applications to finance
| year = 2011
| series=Monographs on Statistics and Applied Probability
| volume=122
| publisher=CRC Press
| isbn = 978-1-43983-574-6 
}}
* {{Cite book
| author = Stein, C.
| title = Approximate computation of expectations
| year = 1986
| publisher = Institute of Mathematical Statistics
| series=Lecture Notes-Monograph Series
| volume=7
| isbn = 0-940600-08-0
}}
* {{Cite journal
|  author = Tikhomirov, A. N.
|  title = Convergence rate in the central limit theorem for weakly dependent random variables
|  journal = Teoriya Veroyatnostei i ee Primeneniya
|  year = 1980
|  volume = 25
|  pages = 800–818
}}  English translation in {{cite journal |  author = Tikhomirov, A. N. |year=1981 |title=On the Convergence Rate in the Central Limit Theorem for Weakly Dependent Random Variables |journal=Theory of Probability & Its Applications |volume=25 |issue=4 |pages=790–809  |doi=10.1137/1125092 }}

==Literature==

The following text is advanced, and gives a comprehensive overview of the normal case
* {{Cite book
|  title = Normal approximation by Stein's method
|  publisher = www.springer.com
|  year = 2011
|  author = Chen, L.H.Y., Goldstein, L., and Shao, Q.M
|  isbn = 978-3-642-15006-7
}}

Another advanced book, but having some introductory character, is
* {{Cite book
|  title = An introduction to Stein's method
|  publisher = Singapore University Press
|  year = 2005
|  author = ed. Barbour, A.D. and Chen, L.H.Y.
|  volume = 4
|  series = Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore
|  isbn = 981-256-280-X
}}

A standard reference is the book by Stein, 
* {{Cite book
| author = Stein, C.
| title = Approximate computation of expectations
| year = 1986
| series = Institute of Mathematical Statistics Lecture Notes, Monograph Series, 7
| isbn = 0-940600-08-0
| publisher = Institute of Mathematical Statistics
| location = Hayward, Calif.
}}
which contains a lot of interesting material, but may be a little hard to understand at first reading.

Despite its age, there are few standard introductory books about Stein's method available.  The following recent textbook has a chapter (Chapter 2) devoted to introducing Stein's method:
* {{Cite book
|  title = A second course in probability
|  year = 2007
|author1=Ross, Sheldon  |author2=Peköz, Erol
 |name-list-style=amp |  isbn = 978-0-9795704-0-7
}}

Although the book
* {{Cite book
|  title = Poisson approximation
|  publisher = The Clarendon Press Oxford University Press
|  year = 1992
|  author = Barbour, A. D. and Holst, L. and Janson, S.
|  volume = 2
|  series = Oxford Studies in Probability
|  isbn = 0-19-852235-5
}}
is by large parts about Poisson approximation, it contains nevertheless a lot of information about the generator approach, in particular in the context of Poisson process approximation.

The following textbook has a chapter (Chapter 10) devoted to introducing Stein's method of Poisson approximation:
* {{Cite book
|  title = Stochastic Processes
|  publisher = Wiley
|  year = 1995
|  author = Sheldon M. Ross 
|  isbn = 978-0471120629 
}}

{{DEFAULTSORT:Stein's Method}}
[[Category:Statistical distance]]
[[Category:Theory of probability distributions]]

{{Sourceattribution|Stein's method}}