Stein’s method for concentration inequalities. (English) Zbl 1116.60056
Summary: We introduce a version of Stein’s method for proving concentration and moment inequalities in problems with dependence. Simple illustrative examples from combinatorics, physics, and mathematical statistics are provided.
MSC:
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 60E15 | Inequalities; stochastic orderings |
| 60C05 | Combinatorial probability |
| 82C22 | Interacting particle systems in time-dependent statistical mechanics |
Keywords:
Concentration inequalities; Random permutations; Gibbs measures; Stein’s method; Curie-Weiss model; Ising modelReferences:
| [1] | Arratia, R.; Goldstein, L.; Gordon, L., Two moments suffice for Poisson approximations: the Chen-Stein method, Ann. Probab., 17, 1, 9-25 (1989) · Zbl 0675.60017 |
| [2] | Arratia, R.; Goldstein, L.; Gordon, L., Poisson approximation and the Chen-Stein method, Statist. Sci., 5, 4, 403-434 (1992) · Zbl 0955.62542 |
| [3] | Baldi, P.; Rinott, Y., On normal approximations of distributions in terms of dependency graphs, Ann. Probab., 17, 4, 1646-1650 (1989) · Zbl 0691.60020 |
| [4] | Barbour, A. D., Stein’s method for diffusion approximations, Probab. Theory Relat. Fields, 84, 3, 297-322 (1990) · Zbl 0665.60008 · doi:10.1007/BF01197887 |
| [5] | Barbour A.D., Holst L., Janson S. (1992) Poisson approximation. In: Oxford Studies in Probability, vol 2. The Clarendon Press, Oxford University Press, New York · Zbl 0746.60002 |
| [6] | Besag, J. E., Statistical analysis of non-lattice data, Statistician, 24, 179-195 (1975) · doi:10.2307/2987782 |
| [7] | Bolthausen, E., An estimate of the remainder in a combinatorial central limit theorem, Z. Wahrsch. Verw. Gebiete, 66, 3, 379-386 (1984) · Zbl 0563.60026 · doi:10.1007/BF00533704 |
| [8] | Bolthausen, E.; Götze, F., The rate of convergence for multivariate sampling statistics, Ann. Statist., 21, 4, 1692-1710 (1993) · Zbl 0798.62023 |
| [9] | Boucheron, S.; Lugosi, G.; Massart, P., Concentration inequalities using the entropy method, Ann. Probab., 31, 3, 1583-1614 (2003) · Zbl 1051.60020 · doi:10.1214/aop/1055425791 |
| [10] | Burkholder, D. L., Distribution function inequalities for martingales, Ann. Probab., 1, 19-42 (1973) · Zbl 0301.60035 |
| [11] | Chatterjee, S.: Concentration inequalities with exchangeable pairs. Ph.D. thesis, Department of Statistics, Stanford University. Available at http://arxiv.org/math.PR/0507526 (2005) |
| [12] | Chatterjee, S.: Concentration of Haar measures, with an application to random matrices. (Submitted, 2005) Available at http://arxiv.org/math.PR/0508518 |
| [13] | Chatterjee, S.; Diaconis, P.; Meckes, E., Exchangeable pairs and Poisson approximation, Probab. Surv., 2, 64-106 (2005) · Zbl 1189.60072 · doi:10.1214/154957805100000096 |
| [14] | Chazottes, J.-R., Collet, P., Külske, C., Redig, F.: Concentration inequalities for random fields via coupling. (Submitted, 2006) Available at http://arxiv.org/math.PR/0503483 · Zbl 1111.60070 |
| [15] | Chen, L. H.Y., Poisson approximation for dependent trials, Ann. Probab., 3, 3, 534-545 (1975) · Zbl 0335.60016 |
| [16] | Diaconis, P.; Graham, R. L., Spearman’s footrule as a measure of disarray, J. R. Statist. Soc. Ser. B, 39, 2, 262-268 (1977) · Zbl 0375.62045 |
| [17] | Diaconis P., Holmes S. (eds) (2004) Stein’s method: expository lectures and applications. In: IMS Lecture Notes—Monograph Series, vol. 46 · Zbl 1079.62024 |
| [18] | Ellis R.S.: Entropy, large deviations, and statistical mechanics. Grund. der Mathemat. Wissenschaften, vol. 271. Springer, New York · Zbl 0566.60097 |
| [19] | Feller, W., An Introduction to Probability Theory and its Applications, vol. I (1968), New York: Wiley, New York · Zbl 0155.23101 |
| [20] | Fulman, J.: Stein’s method and non-reversible Markov chains. In: Stein’s Method: Expository Lectures and Applications, pp. 69-77. IMS Lecture Notes Monogr. Ser., vol. 46. IMS, Beachwood (2004) |
| [21] | Fulman, J., Stein’s method and Plancherel measure of the symmetric group, Trans. Am. Math. Soc., 357, 2, 555-570 (2005) · Zbl 1054.05099 · doi:10.1090/S0002-9947-04-03499-3 |
| [22] | Geyer, C. J.; Thompson, E. A., Constrained Monte Carlo maximum likelihood for dependent data, J. R. Statist. Soc. Ser. B, 54, 3, 657-699 (1992) |
| [23] | Goldstein, L.; Reinert, G., 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 |
| [24] | Hoeffding, W., A combinatorial central limit theorem, Ann. Math. Statist., 22, 4, 558-566 (1951) · Zbl 0044.13702 |
| [25] | Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., 58, 13-30 (1963) · Zbl 0127.10602 · doi:10.2307/2282952 |
| [26] | Jerrum, M.; Sinclair, A., Polynomial-time approximation algorithms for the Ising model, SIAM J. Comput., 22, 5, 1087-1116 (1993) · Zbl 0782.05076 · doi:10.1137/0222066 |
| [27] | Kim, J. H.; Vu, V. H., Divide and conquer martingales and the number of triangles in a random graph, Random Struct. Algor., 24, 2, 166-174 (2004) · Zbl 1041.60042 · doi:10.1002/rsa.10113 |
| [28] | Ledoux, M.: The Concentration of Measure Phenomenon. Am. Math. Soc., Providence, RI (2001) · Zbl 0995.60002 |
| [29] | Luczak, M. J.; McDiarmid, C., Concentration for locally acting permutations, Discrete Math., 265, 1-3, 159-171 (2003) · Zbl 1025.60003 · doi:10.1016/S0012-365X(02)00628-3 |
| [30] | Maurey, B., Construction de suites symétriques, C. R. Acad. Sci. Paris Sér. A-B, 288, 14, A679-A681 (1979) · Zbl 0398.46019 |
| [31] | McDiarmid, C., Concentration for independent permutations, Combin. Probab. Comput., 11, 2, 163-178 (2002) · Zbl 1001.60014 · doi:10.1017/S0963548301005089 |
| [32] | Pickard, D. K., Inference for discrete Markov fields: the simplest nontrivial case, J. Am. Statist. Assoc., 82, 397, 90-96 (1987) · Zbl 0621.62091 · doi:10.2307/2289128 |
| [33] | Raič, M.: CLT-related large deviation bounds based on Stein’s method (preprint, 2004) · Zbl 1127.60024 |
| [34] | Rinott, Y.; Rotar, V., 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 |
| [35] | Shao, Q., Su, Z.: The Berry-Esseen bound for character ratios (preprint, 2004) · Zbl 1093.60014 |
| [36] | Schmuckenschläger, M.: Curvature of nonlocal Markov generators. In: Convex Geometric Analysis: MSRI Publications. vol. 34, pp. 189-197 (1998) · Zbl 0943.60088 |
| [37] | Shorack, G. R.; Wellner, J. A., Empirical processes with applications to statistics (1986), New York: Wiley, New York · Zbl 1170.62365 |
| [38] | Stein, C.: A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In: Proceedings of the 6th Berkeley Symposium on Mathematical Statistics and Probability, vol. II: Probability theory, pp. 583-602 (1972) · Zbl 0278.60026 |
| [39] | Stein, C.: Approximate computation of expectations. IMS Lecture Notes—Monograph Series, vol. 7 (1986) · Zbl 0721.60016 |
| [40] | Talagrand, M., Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes Études Sci. Publ. Math., 81, 73-205 (1995) · Zbl 0864.60013 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
