Fundamentals of Stein’s method. (English) Zbl 1245.60033

Ross, Nathan

Probab. Surv. 8, 210-293 (2011).

Summary: 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 graduate 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.

MSC:

60F05	Central limit and other weak theorems
60C05	Combinatorial probability
05C80	Random graphs (graph-theoretic aspects)

Keywords:

Stein’s method; distributional approximation; concentration of measure inequalities; size-bias distribution; exchangeable pairs

References:

[1]	D. Aldous and J. Fill. Reversible Markov chains and random walks on graphs. , 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. · Zbl 1040.60001
[3]	R. Arratia and L. Goldstein. Size bias, sampling, the waiting time paradox, and infinite divisibility: when is the increment independent? , 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. · Zbl 0675.60017 · doi:10.1214/aop/1176991491
[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. · Zbl 0955.62542
[6]	R. Arratia, L. Gordon, and M. S. Waterman. The Erdős-Rényi law in distribution, for coin tossing and sequence matching. Ann. Statist. , 18(2):539-570, 1990. · Zbl 0712.92016 · doi:10.1214/aos/1176347615
[7]	K. B. Athreya and P. E. Ney. Branching processes . Springer-Verlag, New York, 1972. Die Grundlehren der mathematischen Wissenschaften, Band 196. · Zbl 0259.60002
[8]	F. Avram and D. Bertsimas. On central limit theorems in geometrical probability. Ann. Appl. Probab. , 3(4):1033-1046, 1993. · Zbl 0784.60015 · doi:10.1214/aoap/1177005271
[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. · Zbl 0704.62018
[10]	A. D. Barbour. Poisson convergence and random graphs. Math. Proc. Cambridge Philos. Soc. , 92(2):349-359, 1982. · Zbl 0498.60016 · doi:10.1017/S0305004100059995
[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. · Zbl 0746.60002
[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. · Zbl 0689.05042 · doi:10.1016/0095-8956(89)90014-2
[14]	B. Bollobás. Random graphs , volume 73 of Cambridge Studies in Advanced Mathematics . Cambridge University Press, Cambridge, second edition, 2001.
[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. · Zbl 0985.05047 · doi:10.1002/rsa.1009
[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. · Zbl 1120.68427
[17]	S. Chatterjee. Concentration inequalities with exchangeable pairs. , 2005. Ph.D. dissertation, Stanford University.
[18]	S. Chatterjee. Stein’s method for concentration inequalities. Probab. Theory Related Fields , 138(1-2):305-321, 2007. · Zbl 1116.60056 · doi:10.1007/s00440-006-0029-y
[19]	S. Chatterjee and P. S. Dey. Applications of Stein’s method for concentration inequalities. Ann. Probab. , 38(6):2443-2485, 2010. · Zbl 1203.60023 · doi:10.1214/10-AOP542
[20]	S. Chatterjee, P. Diaconis, and E. Meckes. Exchangeable pairs and Poisson approximation. Probab. Surv. , 2:64-106 (electronic), 2005. · Zbl 1189.60072 · doi:10.1214/154957805100000096
[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. · Zbl 1276.60010
[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. · Zbl 1216.60018 · doi:10.1214/10-AAP712
[23]	S. Chatterjee and Students. Stein’s method course notes. , 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.
[25]	L. H. Y. Chen and Q.-M. Shao. Normal approximation under local dependence. Ann. Probab. , 32(3A):1985-2028, 2004. · Zbl 1048.60020 · doi:10.1214/009117904000000450
[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.
[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. · Zbl 0579.60097
[28]	S. Ghosh and L. Goldstein. Applications of size biased couplings for concentration of measures. Electronic Communications in Probability , 16:70-83, 2011. · Zbl 1227.60021 · doi:10.1214/ECP.v16-1605
[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. · Zbl 1239.60011 · doi:10.1007/s00440-009-0253-3
[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. · Zbl 1087.60021 · doi:10.1239/jap/1127322019
[31]	L. Goldstein. A probabilistic proof of the Lindeberg-Feller central limit theorem. Amer. Math. Monthly , 116(1):45-60, 2009. · Zbl 1163.60008 · doi:10.4169/193009709X469788
[32]	L. Goldstein. A Berry-Esseen bound with applications to counts in the Erdös-Rényi random graph. , 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. · Zbl 0903.60019 · doi:10.1214/aoap/1043862419
[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. · Zbl 0845.60023 · doi:10.2307/3215259
[35]	G. R. Grimmett and D. R. Stirzaker. Probability and random processes . Oxford University Press, New York, third edition, 2001. · Zbl 1015.60002
[36]	W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. , 58:13-30, 1963. · Zbl 0127.10602 · doi:10.2307/2282952
[37]	S. Janson, T. Łuczak, and A. Rucinski. Random graphs . Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
[38]	T. M. Liggett. Interacting particle systems . Classics in Mathematics. Springer-Verlag, Berlin, 2005. Reprint of the 1985 original. · Zbl 1103.82016
[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. · Zbl 1135.62395 · doi:10.1073/pnas.202468099
[40]	R. Lyons, R. Pemantle, and Y. Peres. Conceptual proofs of L log L criteria for mean behavior of branching processes. Ann. Probab. , 23(3):1125-1138, 1995. · Zbl 0840.60077 · doi:10.1214/aop/1176988176
[41]	E. Peköz. Stein’s method for geometric approximation. J. Appl. Probab. , 33(3):707-713, 1996. · Zbl 0865.60014 · doi:10.2307/3215352
[42]	E. Peköz, A. Röllin, and N. Ross. Total variation and local limit error bounds for geometric approximation. , 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. · Zbl 1213.60049 · doi:10.1214/10-AOP559
[44]	J. Pitman. Probabilistic bounds on the coefficients of polynomials with only real zeros. J. Combin. Theory Ser. A , 77(2):279-303, 1997. · Zbl 0866.60016 · doi:10.1006/jcta.1997.2747
[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. · doi:10.1142/9789812567680_0004
[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. · doi:10.1089/cmb.2009.0198
[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. · Zbl 0890.60019 · doi:10.1214/aoap/1043862425
[48]	A. Röllin. A note on the exchangeability condition in Stein’s method. , 2006.
[49]	L. H. Y. Chen and A. Röllin. Stein couplings for normal approximation. , 2010.
[50]	A. Röllin and N. Ross. A probabilistic approach to local limit theorems with applications to random graphs. , 2010. · Zbl 1198.14048
[51]	S. Ross and E. Peköz. A second course in probability . , 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. · Zbl 0627.60045 · doi:10.1007/BF00718031
[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. · Zbl 1093.60014 · doi:10.1090/S0002-9939-05-08177-3
[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. · Zbl 0278.60026
[55]	C. Stein. Approximate computation of expectations . Institute of Mathematical Statistics Lecture Notes-Monograph Series, 7. Institute of Mathematical Statistics, Hayward, CA, 1986. · Zbl 0721.60016
[56]	I. S. Tyurin. Sharpening the upper bounds for constants in Lyapunov’s theorem. Uspekhi Mat. Nauk , 65(3(393)):201-201, 2010. · Zbl 1225.60050 · doi:10.1070/RM2010v065n03ABEH004688
[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. · doi:10.1089/cmb.2010.0056
[58]	M. Waterman. Introduction to computational biology . Chapman & Hall/CRC Interdisciplinary Statistics. CRC Press, 1995.