×

Precise logarithmic asymptotics for the right tails of some limit random variables for random trees. (English) Zbl 1232.60021

Summary: 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 following facts: (i) the random variables we study can be represented as functionals of a Brownian excursion; and (ii) a large deviation principle with good rate function is known explicitly for Brownian excursions. 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 the Wiener index (where we recover results proved by S. Janson and P. Chassaing [Electron. Commun. Probab. 9, 178–187 (2004; Zbl 1060.60095)] by a different method) and for some other examples, a key constant is expressed as the solution to a certain optimization problem, but the precise value of the constant remains unknown.

MSC:

60F10 Large deviations
60C05 Combinatorial probability
60J65 Brownian motion

Citations:

Zbl 1060.60095
PDFBibTeX XMLCite
Full Text: DOI arXiv

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. · Zbl 0791.60008
[2] Aldous D.: The continuum random tree III. Ann. Probab. 21(1), 248–289 (1993) · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[3] Biane P., Pitman J., Yor M.: Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions. Bull. Amer. Math. Soc. (N.S.) 38(4), 435–465 (2001) · Zbl 1040.11061 · doi:10.1090/S0273-0979-01-00912-0
[4] Bousquet-Mélou M., Janson S.: The density of the ISE and local limit laws for embedded trees. Ann. Appl. Probab. 16(3), 1597–1632 (2006) · Zbl 1132.60009 · doi:10.1214/105051606000000213
[5] Cameron R.H., Martin W.T.: Transformations of Wiener integrals under translations. Ann. of Math. 2(45), 386–396 (1944) · Zbl 0063.00696 · doi:10.2307/1969276
[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. · Zbl 0965.68067
[7] Chung K.L.: Excursions in Brownian motion. Ark. Mat. 14(2), 155–177 (1976) · Zbl 0356.60033 · doi:10.1007/BF02385832
[8] Csörgo M., Shi Z., Yor M.: Some asymptotic properties of the local time of the uniform empirical process. Bernoulli 5(6), 1035–1058 (1999) · Zbl 0960.60023 · doi:10.2307/3318559
[9] Davies L.: Tail probabilities for positive random variables with entire characteristic functions of very regular growth. Z. Angew. Math. Mech. 56(3), T334–T336 (1976) · Zbl 0342.60014
[10] Dembo A., Zeitouni O.: Large Deviations Techniques and Applications. Jones and Bartlett Publishers, Boston, MA (1993) · Zbl 0793.60030
[11] J.A. Fill and S. Janson, Brownian excursion representation for the sum of {\(\alpha\)}th powers of subtree sizes for conditioned Galton-Watson trees, in preparation.
[12] Fill J.A., Kapur N.: Limiting distributions for additive functionals on Catalan trees. Theoret. Comput. Sci. 326(1-3), 69–102 (2004) · Zbl 1071.68102 · doi:10.1016/j.tcs.2004.05.010
[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 (n {\(\alpha\)}): asymptotics of moments for {\(\alpha\)} 1, unpublished manuscript.
[15] Flajolet P., Gao Z., Odlyzko A., Richmond B.: The distribution of heights of binary and other simple trees. Combin. Probab. Comput. 2(2), 145–156 (1993) · Zbl 0795.05042 · doi:10.1017/S0963548300000560
[16] Janson S.: Gaussian Hilbert Spaces. Cambridge University Press, Cambridge UK (1997) · Zbl 0887.60009
[17] Janson S.: The Wiener index of simply generated random trees. Random Structures Algorithms 22(4), 337–358 (2003) · Zbl 1025.05021 · doi:10.1002/rsa.10074
[18] Janson S.: Random cutting and records in deterministic and random trees. Random Structures Algorithms 29(2), 139–179 (2006) · Zbl 1120.05083 · doi:10.1002/rsa.20086
[19] Janson S.: Left and right pathlengths in random binary trees. Algorithmica 46(3-4), 419–429 (2006) · Zbl 1106.68085 · doi:10.1007/s00453-006-0099-3
[20] Janson S., Chassaing P.: The center of mass of the ISE and the Wiener index of trees. Electron. Comm. Probab. 9, 178–187 (2004) · Zbl 1060.60095
[21] Kallenberg O.: Foundations of Modern Probability, 2nd Ed. Springer-Verlag, New York (2002) · Zbl 0996.60001
[22] Kasahara Y.: Tauberian theorems of exponential type. J. Math. Kyoto Univ. 18(2), 209–219 (1978) · Zbl 0421.40009
[23] Kennedy D.P.: The distribution of the maximum Brownian excursion. J. Appl. Probab. 13(2), 371–376 (1976) · Zbl 0338.60048 · doi:10.2307/3212843
[24] Knessl C., Szpankowski W.: Quicksort algorithm again revisited. Discrete Math. Theor. Comput. Sci. 3, 43–64 (1999) · Zbl 0947.68042
[25] Marckert J.-F.: The rotation correspondence is asymptotically a dilatation. Random Structures Algorithms 24(2), 118–132 (2004) · Zbl 1034.05016 · doi:10.1002/rsa.10111
[26] Revuz D., Yor M.: Continuous Martingales and Brownian Motion, 3rd Ed. Springer- Verlag, Berlin (1999) · Zbl 0917.60006
[27] Serlet L.: A large deviation principle for the Brownian snake. Stochastic Process. Appl. 67(1), 101–115 (1997) · Zbl 0889.60026 · doi:10.1016/S0304-4149(97)00128-7
[28] Vervaat W.: A relation between Brownian bridge and Brownian excursion. Ann. Probab. 7(1), 143–149 (1979) · Zbl 0392.60058 · doi:10.1214/aop/1176995155
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.