Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 14 (2009) > Paper 92 open journal systems 


Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices

Hanna Döring, Ruhr-Universität Bochum
Peter Eichelsbacher, Ruhr-Universität Bochum


Abstract
We prove the moderate deviation principle for subgraph count statistics of Erdös-Renyi random graphs. This is equivalent in showing the moderate deviation principle for the trace of a power of a Bernoulli random matrix. It is done via an estimation of the log-Laplace transform and the Gärtner-Ellis theorem. We obtain upper bounds on the upper tail probabilities of the number of occurrences of small subgraphs. The method of proof is used to show supplemental moderate deviation principles for a class of symmetric statistics, including non-degenerate U-statistics with independent or Markovian entries.


Full text: PDF

Pages: 2636-2656

Published on: December 12, 2009
Bibliography
  1. Ben Arous, G.; Guionnet, A. Large deviations for Wigner's law and Voiculescu's non-commutative entropy. Probab. Theory Related Fields 108 (1997), no. 4, 517--542. MR1465640 (98i:15026)
  2. Bradley, Richard C. Basic properties of strong mixing conditions. A survey and some open questions. Update of, and a supplement to, the 1986 original. Probab. Surv. 2 (2005), 107--144 (electronic). MR2178042 (2006g:60054)
  3. Catoni, Olivier. Laplace transform estimates and deviation inequalities. Ann. Inst. H. Poincaré Probab. Statist. 39 (2003), no. 1, 1--26. MR1959840 (2003m:60035)
  4. Chatterjee, S.; Dey, P.S. Applications of Stein's method for concentration inequalities. preprint, see arXiv:0906.1034v1 (2009)
  5. Dembo, A.; Guionnet, A.; Zeitouni, O. Moderate deviations for the spectral measure of certain random matrices. Ann. Inst. H. Poincaré Probab. Statist. 39 (2003), no. 6, 1013--1042. MR2010395 (2004k:60092)
  6. Delyon, Bernard; Juditsky, c Anatoly; Liptser, Robert. Moderate deviation principle for ergodic Markov chain. Lipschitz summands. From stochastic calculus to mathematical finance, 189--209, Springer, Berlin, 2006. MR2233540 (2007b:60060)
  7. Dembo, Amir; Zeitouni, Ofer. Large deviations techniques and applications. Second edition. Applications of Mathematics (New York), 38. Springer-Verlag, New York, 1998. xvi+396 pp. ISBN: 0-387-98406-2 MR1619036 (99d:60030)
  8. Eichelsbacher, Peter. Moderate and large deviations for U-processes. Stochastic Process. Appl. 74 (1998), no. 2, 273--296. MR1624408 (99c:60054)
  9. Eichelsbacher, Peter. Moderate deviations for functional U-processes. Ann. Inst. H. Poincaré Probab. Statist. 37 (2001), no. 2, 245--273. MR1819125 (2001m:60061)
  10. Eichelsbacher, Peter; Schmock, Uwe. Rank-dependent moderate deviations of U-empirical measures in strong topologies. Probab. Theory Related Fields 126 (2003), no. 1, 61--90. MR1981633 (2004b:60077)
  11. Janson, Svante. Poisson approximation for large deviations. Random Structures Algorithms 1 (1990), no. 2, 221--229. MR1138428 (93a:60041)
  12. Janson, Svante; Łuczak, Tomasz; Ruciński, Andrzej. An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. Random graphs '87 (Poznań, 1987), 73--87, Wiley, Chichester, 1990. MR1094125 (91m:05168)
  13. Janson, Svante; Łuczak, Tomasz; Rucinski, Andrzej. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. xii+333 pp. ISBN: 0-471-17541-2 MR1782847 (2001k:05180)
  14. Janson, Svante; Oleszkiewicz, Krzysztof; Ruciński, Andrzej. Upper tails for subgraph counts in random graphs. Israel J. Math. 142 (2004), 61--92. MR2085711 (2005e:05126)
  15. Janson, Svante; Ruciński, Andrzej. The infamous upper tail. Probabilistic methods in combinatorial optimization. Random Structures Algorithms 20 (2002), no. 3, 317--342. MR1900611 (2003c:60013)
  16. Janson, Svante; Ruciński, Andrzej. The deletion method for upper tail estimates. Combinatorica 24 (2004), no. 4, 615--640. MR2096818 (2005i:60019)
  17. Kim, J. H.; Vu, V. H. Divide and conquer martingales and the number of triangles in a random graph. Random Structures Algorithms 24 (2004), no. 2, 166--174. MR2035874 (2005d:05135)
  18. Lee, A. J. U-statistics. Theory and practice. Statistics: Textbooks and Monographs, 110. Marcel Dekker, Inc., New York, 1990. xii+302 pp. ISBN: 0-8247-8253-4 MR1075417 (91k:60026)
  19. Nowicki, Krzysztof; Wierman, John C. Subgraph counts in random graphs using incomplete U-statistics methods. Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986). Discrete Math. 72 (1988), no. 1-3, 299--310. MR0975550 (89k:05100)
  20. Ruciński, Andrzej. When are small subgraphs of a random graph normally distributed? Probab. Theory Related Fields 78 (1988), no. 1, 1--10. MR0940863 (89e:60023)
  21. Vu, Van H. A large deviation result on the number of small subgraphs of a random graph. Combin. Probab. Comput. 10 (2001), no. 1, 79--94. MR1827810 (2002d:05112)
  22. Wu, Li Ming. Moderate deviations of dependent random variables related to CLT. Ann. Probab. 23 (1995), no. 1, 420--445. MR1330777 (96f:60047)













Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489