Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 8 (2011) open journal systems 


Fundamentals of Stein's method

Nathan F. Ross, University of California, Berkeley


Abstract
This survey article discusses the main concepts and techniques of Stein's method for distributional approximation by the normal, Poisson, exponential, and geometric distributions, and also its relation to concentration of measure inequalities. The material is presented at a level accessible to beginning raduate students studying probability with the main emphasis on the themes that are common to these topics and also to much of the Stein's method literature.

AMS 2000 subject classifications: Primary 60F05, 60C05; secondary 05C80.

Keywords: Stein's method, distributional approximation, concentration of measure inequalities, size-bias distribution, exchangeable pairs.

Creative Common LOGO

Full Text: PDF


Ross, Nathan F., Fundamentals of Stein's method, Probability Surveys, 8, (2011), 210-293 (electronic). DOI: 10.1214/11-PS182.

References

[1]    D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs. http://www.stat.berkeley.edu/~aldous/RWG/book.html, 2010.

[2]    R. Arratia, A. D. Barbour, and S. Tavaré. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich, 2003. MR2032426

[3]    R. Arratia and L. Goldstein. Size bias, sampling, the waiting time paradox, and infinite divisibility: when is the increment independent? http://arxiv.org/abs/1007.3910, 2011.

[4]    R. Arratia, L. Goldstein, and L. Gordon. Two moments suffice for Poisson approximations: the Chen-Stein method. Ann. Probab., 17(1):9–25, 1989. MR0972770

[5]    R. Arratia, L. Goldstein, and L. Gordon. Poisson approximation and the Chen-Stein method. Statist. Sci., 5(4):403–434, 1990. With comments and a rejoinder by the authors. MR1092983

[6]    R. Arratia, L. Gordon, and M. S. Waterman. The Erd˝o
    s-Rényi law in distribution, for coin tossing and sequence matching. Ann. Statist., 18(2):539–570, 1990. MR1056326

[7]    K. B. Athreya and P. E. Ney. Branching processes. Springer-Verlag, New York, 1972. Die Grundlehren der mathematischen Wissenschaften, Band 196. MR0373040

[8]    F. Avram and D. Bertsimas. On central limit theorems in geometrical probability. Ann. Appl. Probab., 3(4):1033–1046, 1993. MR1241033

[9]    P. Baldi, Y. Rinott, and C. Stein. A normal approximation for the number of local maxima of a random function on a graph. In Probability, statistics, and mathematics, pages 59–81. Academic Press, Boston, MA, 1989. MR1031278

[10]    A. D. Barbour. Poisson convergence and random graphs. Math. Proc. Cambridge Philos. Soc., 92(2):349–359, 1982. MR0671189

[11]    A. D. Barbour and L. H. Y. Chen, editors. An introduction to Stein’s method, volume 4 of Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore. Singapore University Press, Singapore, 2005. Lectures from the Meeting on Stein’s Method and Applications: a Program in Honor of Charles Stein held at the National University of Singapore, Singapore, July 28–August 31, 2003.

[12]    A. D. Barbour, L. Holst, and S. Janson. Poisson approximation, volume 2 of Oxford Studies in Probability. The Clarendon Press Oxford University Press, New York, 1992. Oxford Science Publications. MR1163825

[13]    A. D. Barbour, M. Karoński, and A. Ruciński. A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B, 47(2):125–145, 1989. MR1047781

[14]    B. Bollobás. Random graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2001. MR1864966

[15]    B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády. The degree sequence of a scale-free random graph process. Random Structures Algorithms, 18(3):279–290, 2001. MR1824277

[16]    O. Bousquet, S. Boucheron, and G. Lugosi. Concentration inequalities. In Advanced Lectures on Machine Learning: ML Summer Schools 2003, Lecture Notes in Artificial Intelligence, pages 208–240. Springer, 2004.

[17]    S. Chatterjee. Concentration inequalities with exchangeable pairs. http://arxiv.org/abs/math/0507526, 2005. Ph.D. dissertation, Stanford University. MR2707160

[18]    S. Chatterjee. Stein’s method for concentration inequalities. Probab. Theory Related Fields, 138(1-2):305–321, 2007. MR2288072

[19]    S. Chatterjee and P. S. Dey. Applications of Stein’s method for concentration inequalities. Ann. Probab., 38(6):2443–2485, 2010. MR2683635

[20]    S. Chatterjee, P. Diaconis, and E. Meckes. Exchangeable pairs and Poisson approximation. Probab. Surv., 2:64–106 (electronic), 2005. MR2121796

[21]    S. Chatterjee, J. Fulman, and A. Rollin. Exponential approximation by Stein’s method and spectral graph theory. ALEA Lat. Am. J. Probab. Math. Stat., 8:197–223, 2011.

[22]    S. Chatterjee and Q.-M. Shao. Nonnormal approximation by Stein’s method of exchangeable pairs with application to the Curie-Weiss model. Ann. Appl. Probab., 21(2):464–483, 2011. MR2807964

[23]    S. Chatterjee and Students. Stein’s method course notes. http://www.stat.berkeley.edu/\textasciitildesourav/stat206Afall07.html, 2007.

[24]    L. H. Y. Chen, L. Goldstein, and Q.-M. Shao. Normal approximation by Stein’s method. Probability and its Applications (New York). Springer, Heidelberg, 2011. MR2732624

[25]    L. H. Y. Chen and Q.-M. Shao. Normal approximation under local dependence. Ann. Probab., 32(3A):1985–2028, 2004. MR2073183

[26]    P. Diaconis and S. Holmes, editors. Stein’s method: expository lectures and applications. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 46. Institute of Mathematical Statistics, Beachwood, OH, 2004. Papers from the Workshop on Stein’s Method held at Stanford University, Stanford, CA, 1998. MR2118599

[27]    P. Donnelly and D. Welsh. The antivoter problem: random 2-colourings of graphs. In Graph theory and combinatorics (Cambridge, 1983), pages 133–144. Academic Press, London, 1984. MR0777170

[28]    S. Ghosh and L. Goldstein. Applications of size biased couplings for concentration of measures. Electronic Communications in Probability, 16:70–83, 2011. MR2763529

[29]    S. Ghosh and L. Goldstein. Concentration of measures via size-biased couplings. Probability Theory and Related Fields, 149:271–278, 2011. 10.1007/s00440-009-0253-3. MR2773032

[30]    L. Goldstein. Berry-Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing. J. Appl. Probab., 42(3):661–683, 2005. MR2157512

[31]    L. Goldstein. A probabilistic proof of the Lindeberg-Feller central limit theorem. Amer. Math. Monthly, 116(1):45–60, 2009. MR2478752

[32]    L. Goldstein. A Berry-Esseen bound with applications to counts in the Erdös-Rényi random graph. http://arxiv.org/abs/1005.4390, 2010.

[33]    L. Goldstein and G. Reinert. Stein’s method and the zero bias transformation with application to simple random sampling. Ann. Appl. Probab., 7(4):935–952, 1997. MR1484792

[34]    L. Goldstein and Y. Rinott. Multivariate normal approximations by Stein’s method and size bias couplings. J. Appl. Probab., 33(1):1–17, 1996. MR1371949

[35]    G. R. Grimmett and D. R. Stirzaker. Probability and random processes. Oxford University Press, New York, third edition, 2001. MR2059709

[36]    W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58:13–30, 1963. MR0144363

[37]    S. Janson, T. Łuczak, and A. Rucinski. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. MR1782847

[38]    T. M. Liggett. Interacting particle systems. Classics in Mathematics. Springer-Verlag, Berlin, 2005. Reprint of the 1985 original. MR2108619

[39]    R. A. Lippert, H. Huang, and M. S. Waterman. Distributional regimes for the number of k-word matches between two random sequences. Proc. Natl. Acad. Sci. USA, 99(22):13980–13989 (electronic), 2002. MR1944413

[40]    R. Lyons, R. Pemantle, and Y. Peres. Conceptual proofs of Llog L criteria for mean behavior of branching processes. Ann. Probab., 23(3):1125–1138, 1995. MR1349164

[41]    E. Peköz. Stein’s method for geometric approximation. J. Appl. Probab., 33(3):707–713, 1996. MR1401468

[42]    E. Peköz, A. Röllin, and N. Ross. Total variation and local limit error bounds for geometric approximation. http://arxiv.org/abs/1005.2774, 2010. To appear in Bernoulli.

[43]    E. A. Peköz and A. Röllin. New rates for exponential approximation and the theorems of Rényi and Yaglom. Ann. Probab., 39(2):587–608, 2011. MR2789507

[44]    J. Pitman. Probabilistic bounds on the coefficients of polynomials with only real zeros. J. Combin. Theory Ser. A, 77(2):279–303, 1997. MR1429082

[45]    G. Reinert. Three general approaches to Stein’s method. In An introduction to Stein’s method, volume 4 of Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., pages 183–221. Singapore Univ. Press, Singapore, 2005. MR2235451

[46]    G. Reinert, D. Chew, F. Sun, and M. S. Waterman. Alignment-free sequence comparison. I. Statistics and power. J. Comput. Biol., 16(12):1615–1634, 2009. MR2578699

[47]    Y. Rinott and V. Rotar. On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted U-statistics. Ann. Appl. Probab., 7(4):1080–1105, 1997. MR1484798

[48]    A. Röllin. A note on the exchangeability condition in Stein’s method. http://arxiv.org/abs/math/0611050v1, 2006.

[49]    L. H. Y. Chen and A. Röllin. Stein couplings for normal approximation. http://arxiv.org/abs/1003.6039, 2010.

[50]    A. Röllin and N. Ross. A probabilistic approach to local limit theorems with applications to random graphs. http://arxiv.org/abs/1011.3100, 2010.

[51]    S. Ross and E. Peköz. A second course in probability. www.ProbabilityBookstore.com, Boston, 2007.

[52]    A. Ruciński. When are small subgraphs of a random graph normally distributed? Probab. Theory Related Fields, 78(1):1–10, 1988. MR0940863

[53]    Q.-M. Shao and Z.-G. Su. The Berry-Esseen bound for character ratios. Proc. Amer. Math. Soc., 134(7):2153–2159 (electronic), 2006. MR2215787

[54]    C. Stein. A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. II: Probability theory, pages 583–602, Berkeley, Calif., 1972. Univ. California Press. MR0402873

[55]    C. Stein. Approximate computation of expectations. Institute of Mathematical Statistics Lecture Notes—Monograph Series, 7. Institute of Mathematical Statistics, Hayward, CA, 1986. MR0882007

[56]    I. S. Tyurin. Sharpening the upper bounds for constants in Lyapunov’s theorem. Uspekhi Mat. Nauk, 65(3(393)):201–201, 2010. MR2682728

[57]    L. Wan, G. Reinert, F. Sun, and M. S. Waterman. Alignment-free sequence comparison (II): theoretical power of comparison statistics. J. Comput. Biol., 17(11):1467–1490, 2010. MR2739743

[58]    M. Waterman. Introduction to computational biology. Chapman & Hall/CRC Interdisciplinary Statistics. CRC Press, 1995.




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787