Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-10T07:26:12.002Z Has data issue: false hasContentIssue false
  • English
  • Français

CLT-related large deviation bounds based on Stein's method

Part of: Sampling theory, sample surveys Graph theory Limit theorems

Published online by Cambridge University Press:  01 July 2016

Martin Raič
Martin Raič*
Affiliation:
University of Ljubljana
*
∗ Postal address: Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia. Email address: martin.raic@fmf.uni-lj.si
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Large deviation estimates are derived for sums of random variables with certain dependence structures, including finite population statistics and random graphs. The argument is based on Stein's method, but with a novel modification of Stein's equation inspired by the Cramér transform.

Keywords

Large deviationscentral limit theoremrandom graphsfinite population statistics

MSC classification

Primary: 60F10: Large deviations
Secondary: 60F05: Central limit and other weak theorems 05C80: Random graphs 62D05: Sampling theory, sample surveys

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 39 , Issue 3 , September 2007 , pp. 731 - 752
Copyright
Copyright © Applied Probability Trust 2007 

References

Baldi, P., Rinott, Y. and Stein, C. (1989). A normal approximation for the number of local maxima of a random function on a graph. In Probability, Statistics, and Mathematics, Academic Press, Boston, MA, pp. 59–81.Google Scholar
Barbour, A. D. (1982). Poisson convergence and random graphs. Math. Proc. Camb. Philos. Soc. 92, 349–359.Google Scholar
Barbour, A. D. (1990). Stein's method for diffusion approximations. Prob. Theory Relat. Fields 84, 297–322.Google Scholar
Barbour, A. D. and Chen, L. H. Y. (eds) (2005). An Introduction to Stein's Method. World Scientific, Singapore.CrossRefGoogle Scholar
Barbour, A. D. and Chen, L. H. Y. (2005). Stein's Method and Applications. World Scientific, Singapore.Google Scholar
Barbour, A. D., Karoński, M. and Ruciński, A. (1989). A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B 47, 125–145.Google Scholar
Bolthausen, E. (1984). An estimate of the remainder in a combinatorial central limit theorem. Z. Wahrscheinlichkeitsth. 66, 379–386.Google Scholar
Chen, L. H. Y. and Shao, Q.-M. (2001). A non-uniform Berry–Esseen bound via Stein's method. Prob. Theory Relat. Fields 120, 236–254.Google Scholar
Chen, L. H. Y. and Shao, Q.-M. (2007). Normal approximation for nonlinear statistics using a concentration inequality approach. Bernoulli 13, 581–599.Google Scholar
Chen, L. H. Y. and Shao, Q.-M. (2004). Normal approximation under local dependence. Ann. Prob. 32, 1985–1985.CrossRefGoogle Scholar
Cramér, H. (1938). Sur un nouveau théorème limite de la théorie des probabilités. In Colloque Consacre à la Théorie des Probabilités 736, Hermann, Paris, pp. 5–23.Google Scholar
Dembo, A. and Rinott, Y. (1996). Some examples of normal approximations by Stein's method. In Random Discrete Structures (IMA Vol. Math. Appl. 76). Springer, New York, pp. 25–44.Google Scholar
Goldstein, L. and Rinott, Y. (1996). Multivariate normal approximations by Stein's method and size bias couplings. J. Appl. Prob. 33, 1–17.Google Scholar
Gorchakov, A. B. (1995). Upper bounds for cumulants of the sum of multi-indexed random variables. Discrete Math Appl. 5, 317–331.Google Scholar
Gorchakov, A. B. (1997). Explicit bounds for probabilities of large deviations of sums of random vectors with a given graph of dependencies. In Probabilistic Methods in Discrete Mathematics (Petrozavodsk, 1996), VSP, Utrecht, pp. 219–230.Google Scholar
Götze, F. (1991). On the rate of convergence in the multivariate CLT. Ann. Prob. 19, 724–739.Google Scholar
Hallin, M. and Puri, M. L. (1992). Some asymptotic results for a broad class of nonparametric statistics. J. Statist. Planning Infer. 32, 165–196.Google Scholar
Ho, S.-T. and Chen, L. H. Y. (1978). An Lp bound for the remainder in a combinatorial central limit theorem. Ann. Prob. 6, 231–249.Google Scholar
Janson, S. (1990). Poisson approximation for large deviations. Random Structures Algorithms 1, 221–229.CrossRefGoogle Scholar
Janson, S. (2004). Large deviations for sums of partly dependent random variables. Random Structures Algorithms 24, 234–248.Google Scholar
Janson, S., Oleszkiewicz, K. and Ruciński, A. (2004). Upper tails for subgraph counts in random graphs. Israel J. Math. 142, 61–92.Google Scholar
Kallenberg, W. C. M. (1982). Cramér type large deviations for simple linear rank statistics. Z. Wahrscheinlichkeitsth. 60, 403–409.CrossRefGoogle Scholar
Kokic, P. N. and Weber, N. C. (1995). Large deviation probabilities for U-statistics based on samples from finite populations. In Exploring Stochastic Laws, VSP, Utrecht, pp. 175–181.Google Scholar
Nandi, H. K. and Sen, P. K. (1963). On the properties of U-statistics when the observations are not independent. II. Unbiased estimation of the parameters of a finite population. Calcutta Statist. Assoc. Bull. 12, 124–148.Google Scholar
O'Connell, N. (1998). Some large deviation results for sparse random graphs. Prob. Theory Relat. Fields 110, 277–285.Google Scholar
Raič, M. (2004). A multivariate CLT for decomposable random vectors with finite second moments. J. Theoret. Prob. 17, 573–603.Google Scholar
Rinott, Y. (1994). On normal approximation rates for certain sums of dependent random variables. J. Comput. Appl. Math. 55, 135–143.CrossRefGoogle Scholar
Rinott, Y. and Rotar, V. (1996). A multivariate CLT for local dependence with n−1/2log n rate and applications to multivariate graph related statistics. J. Multivariate Anal. 56, 333–350.Google Scholar
Rinott, Y. and Rotar, V. (1997). On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted U-statistics. Ann. Appl. Prob. 7, 1080–1105.Google Scholar
Robinson, J. (1977). Large deviation probabilities for samples from a finite population. Ann. Prob. 5, 913–925.Google Scholar
Rudzkis, R., Saulis, L. and Statulevičius, V. (1978). A general lemma on probabilities of large deviations. Lithuanian Math. J.. 18, 226–238.Google Scholar
Saulis, L. and Statulevičius, V. (1991). Limit Theorems for Large Deviations (Math. Appl. (Soviet Ser.) 73). Kluwer, Dordrecht.Google Scholar
Schneller, W. (1989). Edgeworth expansions for linear rank statistics. Ann. Statist. 17, 1103–1123.Google Scholar
Statulevičius, V. A. (1966). On large deviations. Z. Wahrscheinlichkeitsth. 6, 133–144.Google Scholar
Stein, C. (1972). A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proc. Sixth Berkeley Symp. Math. Statist. Prob. (University of California, Berkeley, 1970/1971), Vol. II, Probability Theory, University of California Press, Berkeley, pp. 583–602.Google Scholar
Stein, C. (1986). Approximate Computation of Expectations (Instit. Math. Statist. Lecture Notes Monogr. Ser. 7). Institute of Mathematical Statistics, Hayward, CA.Google Scholar