×

zbMATH — the first resource for mathematics

The depth first processes of Galton-Watson trees converge to the same Brownian excursion. (English) Zbl 1049.05026
The authors deduce relations between five depth processes associated with a critical Galton-Watson process which imply that all five processes (suitably normalized) converge to the same Brownian excursion. This yields an alternative proof of a result of D. Aldous [Ann. Probab. 21, No. 1, 248–289 (1993; Zbl 0791.60009)] that avoids the use of the existence of the limiting continuum random tree. The authors’ approach also permits them, among other things, to determine some concentration inequalities and bounds for large or moderate deviations for some functionals of trees or discrete excursions.

MSC:
05C05 Trees
60F99 Limit theorems in probability theory
60G50 Sums of independent random variables; random walks
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] ALDOUS, D. (1991). The continuum random tree. II. An overview. In Stochastic Analy sis (M. T. Barlow and N. H. Bingham, eds.) 23-70. Cambridge Univ. Press. · Zbl 0722.60013 · doi:10.1214/aop/1176990534
[2] ALDOUS, D. (1993). The continuum random tree. III. Ann. Probab. 21 248-289. · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[3] ALDOUS, D. (1998). Brownian excursion conditioned on its local time. Elect. Comm. Probab. 3 79-90. · Zbl 0914.60049 · emis:journals/EJP-ECP/EcpVol3/paper10.abs.html · eudml:119786
[4] CHASSAING, P., MARCKERT, J. F. and YOR, M. (2000). The height and width of simple trees. In Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities (D. Gardy and A. Mokkadem, eds.) 17-30. Birkhäuser, Boston. · Zbl 0965.68067
[5] CHASSAING, P. and MARCKERT, J. F. (2001). Parking functions, empirical processes, and the width of rooted labeled trees. Elec. J. Combin. 8 R14. · Zbl 0974.05025 · emis:journals/EJC/Volume_8/Abstracts/v8i1r14.html · eudml:121402
[6] CORMEN, T. H., LEISERSON, C. E. and RIVEST, R. L. (1990). Introduction to Algorithms. MIT Press. · Zbl 1158.68538
[7] CSAKI, E. and MOHANTY, S. G. (1981). Excursion and meander in random walk. Canad. J. Statist. 9 57-70. JSTOR: · Zbl 0478.60076 · doi:10.2307/3315296 · links.jstor.org
[8] DRMOTA, M. (1994). The height distribution of leaves in rooted trees. Discrete Math. Appl. 4 45-58. · Zbl 0801.60074 · doi:10.1515/dma.1994.4.1.45
[9] DRMOTA, M. (1996). On nodes of given degree in random trees. In Probabilistic Methods in Discrete Mathematics (V. F. Kolchin, V. Ya. Kozlov, V. V. Mazalov, Yu. L. Pavlov and Yu. V. Prokhorov, eds.). VSP, Zeist, The Netherlands. · Zbl 0917.60086
[10] DRMOTA, M. and GITTENBERGER, B. (1997). On the profile of random trees. Random Structures Algorithms 10 421-451. · Zbl 0882.60084 · doi:10.1002/(SICI)1098-2418(199707)10:4<421::AID-RSA2>3.0.CO;2-W
[11] DUQUESNE, T. and LE GALL, J. F. (2002). Random Trees, Lévy Processes and Spatial Branching Processes. Astérisque 281. · Zbl 1037.60074
[12] DURRETT, R. T., IGLEHART, R. D. L. and MILLER, D. R. (1977). Weak convergence to Brownian meander and Brownian excursion. Ann. Probab. 5 117-129. · Zbl 0356.60034 · doi:10.1214/aop/1176995895
[13] FELLER, W. (1971). An Introduction to Probability Theory and Its Applications 2, 2nd ed. Wiley, New York. · Zbl 0219.60003
[14] FLAJOLET, P., GOURDON, X. and MARTINEZ, C. (1997). Patterns in random binary search trees. Random Structures Algorithms 11 223-244. · Zbl 0895.60010 · doi:10.1002/(SICI)1098-2418(199710)11:3<223::AID-RSA2>3.0.CO;2-2
[15] FUK, D. H. and NAGAEV, S. V. (1971). Probability inequalities for sums of independent random variables. Theory Probab. Appl. 16 643-660. · Zbl 0259.60024 · doi:10.1137/1116071
[16] GUTJAHR, W. and PFLUG, G. C. (1992). The asy mptotic contour process of a binary tree is a Brownian excursion. Stochastic Process. Appl. 41 69-89. · Zbl 0757.60074 · doi:10.1016/0304-4149(92)90147-I
[17] KENNEDY, D. P. (1976). The distribution of the maximum Brownian excursion. J. Appl. Probab. 13 371-376. JSTOR: · Zbl 0338.60048 · doi:10.2307/3212843 · links.jstor.org
[18] LE GALL, J. F. (2000). Lévy processes and branching processes. Courses Notes.
[19] LE GALL, J. F. and LE JAN, Y. (1998). Branching processes in Lévy processes: The exploration process. Ann. Probab. 26 213-252. · Zbl 0948.60071 · doi:10.1214/aop/1022855417
[20] LIMIC, V. (2000). On the behavior of LIFO preemptive resume queues in heavy traffic. Electron. Comm. Probab. 5 13-27. · Zbl 0955.60097 · emis:journals/EJP-ECP/EcpVol5/paper2.abs.html · eudml:120804
[21] LIMIC, V. (2001). A LIFO queue in heavy traffic. Ann. Appl. Probab. 11 301-331. · Zbl 1015.60079
[22] MARCKERT, J. F. (2000). The contour of size n general planar trees. Preprint 53-00, Univ. Versailles.
[23] MEIR, A. and MOON, J. W. (1978). On the altitude of nodes in random trees. Canad. J. Math. 30 997-1015. · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[24] OTTER, R. (1949). The multiplicative process. Ann. Math. Statist. 20 206-224. · Zbl 0033.38301 · doi:10.1214/aoms/1177730031
[25] PETROV, V. V. (1975). Sums of Independant Random Variables. Springer, Berlin.
[26] PORT, S. C. (1994). Theoretical Probability for Applications. Wiley, New York. · Zbl 0860.60001
[27] STEy AERT, J. M. and FLAJOLET, P. (1983). Patterns and pattern-matching in trees: An analysis. Inform. Control 58 19-58. · Zbl 0567.68053 · doi:10.1016/S0019-9958(83)80056-4
[28] TAKÁCS, L. (1993). Limit distributions for queues and random rooted trees. J. Appl. Math. Stochastic Anal. 6 189-216. · Zbl 0791.60084 · doi:10.1155/S1048953393000176 · eudml:46950
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.