Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T18:36:30.208Z Has data issue: false hasContentIssue false
  • English
  • Français

Random subgraph counts and U-statistics: multivariate normal approximation via exchangeable pairs and embedding

Part of: Graph theory Distribution theory Limit theorems

Published online by Cambridge University Press:  14 July 2016

Gesine Reinert  and
Adrian Röllin
Gesine Reinert*
Affiliation:
University of Oxford
Adrian Röllin*
Affiliation:
National University of Singapore
*
∗Postal address: Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK.
∗∗Postal address: Department of Statistics and Applied Probability, National University of Singapore, 6 Science Drive 2, Singapore 117546. Email address: [email protected]
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.

In Reinert and Röllin (2009) a new approach - called the ‘embedding method’ - was introduced, which allows us to make use of exchangeable pairs for normal and multivariate normal approximations with Stein's method in cases where the corresponding couplings do not satisfy a certain linearity condition. The key idea is to embed the problem into a higher-dimensional space in such a way that the linearity condition is then satisfied. Here we apply the embedding to U-statistics as well as to subgraph counts in random graphs.

Keywords

Multivariate normal distributionU-statisticsrandom graph statisticsStein's methodexchangeable pair

MSC classification

Secondary: 60F05: Central limit and other weak theorems 62E17: Approximations to distributions (nonasymptotic) 05C80: Random graphs
Type
Research Article
Information
Journal of Applied Probability , Volume 47 , Issue 2 , June 2010 , pp. 378 - 393
Copyright
Copyright © Applied Probability Trust 2010 

Footnotes

Supported in part by BBsrc and EPSRC Through OCISB.

Supported in part by the Swiss National Science Foundation project PBZH2—117033.

References

[1] Bolthausen, E. (1982). Exact convergence rates in some martingale central limit theorems. Ann. Prob. 10, 672–688.Google Scholar
[2] Bolthausen, E. and Götze, F. (1993). The rate of convergence for multivariate sampling statistics. Ann. Statist. 21, 1692–1710.Google Scholar
[3] Chatterjee, S. (2006). A generalization of the Lindeberg principle. Ann. Prob. 34, 2061–2076.Google Scholar
[4] Chatterjee, S. and Meckes, E. (2008). Multivariate normal approximation using exchangeable pairs. ALEA Lat. Amer. J. Prob. Math. Statist. 4, 257–283.Google Scholar
[5] Janson, S. and Luczak, M. J. (2008). Susceptibility in subcritical random graphs. J. Math. Phys. 49, 125207, 23 pp.Google Scholar
[6] Janson, S. and Nowicki, K. (1991). The asymptotic distributions of generalized U-statistics with applications to random graphs. Prob. Theory Relat. Fields 90, 341–375.Google Scholar
[7] Lee, A. J. (1990). U-Statistics (Statist. Text. Monogr. 110). Marcel Dekker, New York.Google Scholar
[8] Meckes, E. (2009). On Stein's method for multivariate normal approximation. In High Dimensional Probability V: The Luminy Volume, eds Houdré, C. et al., Institute of Mathematical Statistics, Beachwood, OH, pp. 153–178.CrossRefGoogle Scholar
[9] Nourdin, I., Peccati, G. and Reinert, G. (2009). Stein's method and stochastic analysis of Rademacher functionals. Preprint. Available at http://arxiv.org/abs/0810.2890v3.Google Scholar
[10] Raič, M. (2004). A multivariate CLT for decomposable random vectors with finite second moments. J. Theoret. Prob. 17, 573–603.CrossRefGoogle Scholar
[11] Reinert, G. and Röllin, A. (2009). Multivariate normal approximation with Stein's method of exchangeable pairs under a general linearity condition. Ann. Prob. 37, 2150–2173.Google Scholar
[12] Rinott, Y. and Rotar', V. (1996). A multivariate CLT for local dependence with n{−1/2}log n rate and applications to multivariate graph related statistics. J. Multivariate Anal. 56, 333–350.Google Scholar
[13] 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
[14] Rinott, I. and Rotar', V. I. (1998). Some estimates for the rate of convergence in the CLT for martingales. I. Theory Prob. Appl. 43, 604–619.Google Scholar
[15] Stein, C. (1972). A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proc. 6th Berkeley Symp. Math. Statist. Prob., Vol. II, University California Press, pp. 583–602.Google Scholar
[16] Stein, C. (1986). Approximate Computation of Expectations (Inst. Math. Statist. Lecture Notes Monogr. Ser. 7). Institute of Mathematical Statistics, Hayward, CA.Google Scholar