<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 4" %>
Precise Logarithmic Asymptotics for the Right Tails of Some Limit Random Variables for Random Trees
James Allen Fill1 and Svante Janson2
1Department of Applied Mathematics and Statistics, The Johns Hopkins University, 302 Whitehead Hall, 3400 North Charles Street, Baltimore, MD 21218-2682, USA
2Department of Mathematics, Uppsala University, P.O. Box 480, SE-751~06 Uppsala, Sweden
Annals of Combinatorics 12 (4) pp.399-412 December, 2008
AMS Subject Classification: 60F10; 60C05, 60J65
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.
Keywords: large deviations, tail asymptotics, Galton-Watson trees, simply generated families of trees, Brownian excursion, variational problems, total path length, Wiener index


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.