Precise Logarithmic Asymptotics for the
Right Tails of Some Limit
Random Variables for Random Trees

James Allen Fill^{1} and Svante Janson^{2}
^{1}Department of Applied Mathematics and Statistics, The Johns
Hopkins University, 302 Whitehead Hall,
3400 North Charles Street,
Baltimore, MD 21218-2682, USA
^{2}Department of Mathematics, Uppsala University, P.O. Box 480,
SE-751~06 Uppsala, Sweden
**AMS Subject Classification: **60F10; 60C05, 60J65
**Keywords: **large
deviations, tail asymptotics, Galton-Watson trees,
simply generated families of trees, Brownian excursion, variational
problems, total path length, Wiener index

jimfill@jhu.edu

svante.janson@math.uu.se

Annals of Combinatorics 12 (4) pp.399-412 December, 2008

Abstract:

For certain random
variables that arise as limits of functionals of random
finite trees, we obtain precise asymptotics for the
logarithm of the right-hand tail. Our results are
based on the facts (i) that the random variables we
study can be represented as functionals of a Brownian
excursion and (ii) that a large deviation principle
with good rate function is known explicitly for
Brownian excursion. Examples include limit
distributions of the total path length and of the
Wiener index in conditioned Galton-Watson trees (also
known as simply generated trees). In the case of Wiener
index (where we recover results proved by Svante Janson
and Philippe Chassaing by a different method) and for
some other examples, a key constant is expressed as the
solution to a certain optimization problem, but the
constant's precise value remains unknown.
References:

1. D. Aldous, The continuum random tree II: an overview, In: Stochastic Analysis, London Math. Soc. Lecture Note Ser., Vol. 167, M.T. Barlow and N.H. Bingham, Eds. Cambridge Univ. Press, Cambridge, (1991) pp. 23-70.

2. D. Aldous, The continuum random tree III, Ann. Probab. 21 (1) (1993) 248-289.

3. P. Biane, J. Pitman, and M. Yor, Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions, Bull. Amer. Math. Soc. (N.S.) 38 (4) (2001) 435-465.

4. M. Bousquet-M´elou and S. Janson, The density of the ISE and local limit laws for embedded trees, Ann. Appl. Probab. 16 (3) (2006) 1597-1632.

5. R.H. Cameron and W.T. Martin, Transformations of Wiener integrals under translations, Ann. of Math. (2) 45 (1944) 386-396.

6. P. Chassaing, J.F. Marckert, and M. Yor, The height and width of simple trees, In: Mathematics and Computer Science, Birkh¨auser, Basel, (2000) pp. 17-30.

7. K.L. Chung, Excursions in Brownian motion, Ark. Mat. 14 (2) (1976) 155-177.

8. M. Cs¨orgo, Z. Shi, and M. Yor, Some asymptotic properties of the local time of the uniform empirical process, Bernoulli 5 (1999) (6) 1035-1058.

9. L. Davies, Tail probabilities for positive random variables with entire characteristic functions of very regular growth, Z. Angew. Math. Mech. 56 (3) (1976) T334-T336.

10. A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Jones and Bartlett Publishers, Boston, MA, 1993.

11. J.A. Fill and S. Janson, Brownian excursion representation for the sum of ath powers of subtree sizes for conditioned Galton-Watson trees, in preparation.

12. J.A. Fill and N. Kapur, Limiting distributions for additive functionals on Catalan trees, Theoret. Comput. Sci. 326 (1-3) (2004) 69-102.

13. J.A. Fill and N. Kapur, An invariance principle for simply generated families of trees, unpublished manuscript.

14. J.A. Fill and N. Kapur, Catalan trees with toll (na): asymptotics of moments for a›=1, unpublished manuscript.

15. P. Flajolet, Z. Gao, A. Odlyzko, and B. Richmond, The distribution of heights of binary and other simple trees, Combin. Probab. Comput. 2 (2) (1993) 145-156.

16. S. Janson, Gaussian Hilbert Spaces, Cambridge University Press, Cambridge, UK, 1997.

17. S. Janson, The Wiener index of simply generated random trees, Random Structures Algorithms 22 (4) (2003) 337-358.

18. S. Janson, Random cutting and records in deterministic and random trees, Random Structures Algorithms 29 (2) (2006) 139-179.

19. S. Janson, Left and right pathlengths in random binary trees, Algorithmica 46 (3-4) (2006) 419-429.

20. S. Janson and P. Chassaing, The center of mass of the ISE and the Wiener index of trees, Electron. Comm. Probab. 9 (2004) 178-187.

21. O. Kallenberg, Foundations of Modern Probability, 2nd Ed., Springer-Verlag, New York, 2002.

22. Y. Kasahara, Tauberian theorems of exponential type, J. Math. Kyoto Univ. 18 (2) (1978) 209-219.

23. D.P. Kennedy, The distribution of the maximum Brownian excursion, J. Appl. Probab. 13 (2) (1976) 371-376.

24. C. Knessl and W. Szpankowski, Quicksort algorithm again revisited, Discrete Math. Theor. Comput. Sci. 3 (1999) 43-64.

25. J.-F. Marckert, The rotation correspondence is asymptotically a dilatation, Random Structures Algorithms 24 (2) (2004) 118-132.

26. D. Revuz and M. Yor, Continuous Martingales and Brownian Motion, 3rd Ed., Springer- Verlag, Berlin, 1999.

27. L. Serlet, A large deviation principle for the Brownian snake, Stochastic Process. Appl. 67 (1) (1997) 101-115.

28. W. Vervaat, A relation between Brownian bridge and Brownian excursion, Ann. Probab. 7 (1) (1979) 143-149.