Abstract.
We study the inhomogeneous continuum random trees (ICRT) that arise as weak limits of birthday trees. We give a description of the exploration process, a function defined on [0,1] that encodes the structure of an ICRT, and also of its width process, determining the size of layers in order of height. These processes turn out to be transformations of bridges with exchangeable increments, which have already appeared in other ICRT related topics such as stochastic additive coalescence. The results rely on two different constructions of birthday trees from processes with exchangeable increments, on weak convergence arguments, and on general theory on continuum random trees.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aldous, D.J.: The continuum random tree I. Ann. Probab. 19, 1–28 (1991)
Aldous, D.J.: The continuum random tree II: an overview. In: M.T. Barlow and N.H. Bingham, (eds), Stochastic Analysis. Cambridge University Press, pp. 23–70, 1991
Aldous, D.J.: The continuum random tree III. Ann. Probab. 21, 248–289 (1993)
Aldous, D.J., Miermont, G., Pitman, J.: Brownian Bridge Asymptotics for Random p-Mappings. Electr. J. Probab. 9, 37–56 (2004)
Aldous, D.J., Miermont, G., Pitman, J.: Weak Convergence of Random p-Mappings and the Exploration Process of the Inhomogeneous Continuum Random Tree. arXiv:math.PR/0401115
Aldous, D.J., Pitman, J.: Brownian bridge asymptotics for random mappings. Random Struct. Algorithms 5, 487–512 (1994)
Aldous, D.J., Pitman, J.: The standard additive coalescent. Ann. Probab 26, 1703–1726 (1998)
Aldous, D.J., Pitman, J.: A family of random trees with random edge-lengths. Random Struct. Algorithms 15, 176–195 (1999)
Aldous, D.J., Pitman, J.: Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent. Probab. Th. Rel. Fields 118, 455–482 (2000)
Aldous, D.J., Pitman, J.: Invariance principles for non-uniform random mappings and trees. In: V. Malyshev and A.M. Vershik, (eds.), Asymptotic Combinatorics with Applications in Mathematical Physics. Kluwer Academic Publishers, pp. 113–147, 2002
Bertoin, J.: On the local rate of growth of Lévy processes with no positive jumps. Stoch. Proc. App. 55, 91–100 (1995)
Bertoin, J.: A fragmentation process connected to Brownian motion. Probab. Theory Relat. Fields 117, 289–301 (2000)
Bertoin, J.: Eternal additive coalescent and certain bridges with exchangeable increments. Ann. Probab. 29, 344–360 (2001)
Biane, P., Yor, M.: Sur la loi des temps locaux browniens pris en un temps exponentiel. In: Séminaire de Probabilités XXII. Lecture Notes in Math. 1321, Springer, pp. 454–466, 1988
Camarri, M., Pitman, J.: Limit distributions and random trees derived from the birthday problem with unequal probabilities. Electron. J. Probab. 5(2), 1–18 (2000)
Chassaing, P., Louchard, G.: Phase transition for parking blocks, Brownian excursion and coalescence. Random Struct. Algorithms 21, 76–119 (2002)
Duquesne, T., Le Gall, J.-F.: Random trees, Lévy processes and spatial branching processes. Astérisque 281, (2002)
Durrett, R.: Probability: theory and examples. Duxbury Press, Belmont, CA, second edition, 1996
Jeulin, T.: Application de la théorie du grossissement à l’étude des temps locaux browniens. In: T. Jeulin and M. Yor (eds.), Grossissements de filtrations: exemples et applications. Lecture notes in Maths 1118, Springer, Berlin, 1985
Kallenberg, O.: Canonical representations and convergence criteria for processes with interchangeable increments. Z. Wahrsch. Verw. Gebiete 27, 23–36 (1973)
Kallenberg, O.: Path properties for processes with independent and interchangeable increments. Z. Wahrsch. Verw. Gebiete 28, 257–271 (1974)
Kersting, G.: On the height profile of a conditioned Galton-Watson tree. Preprint, 1998
Knight, F.B.: The uniform law for exchangeable and Lévy process bridges. Hommage à P. A. Meyer et J. Neveu. Astérisque 236, 171–188 (1996)
Le Gall, J.-F.: The uniform tree in a Brownian excursion. Probab. Th. Rel. Fields 96, 369–383 (1993)
Le Gall, J.-F.: Brownian excursions, trees and measure-valued branching processes. Ann. Probab. 19, 1299–1439 (1991)
Le Gall, J.-F., Le Jan, Y.: Branching processes in Lévy processes: The exploration process. Ann. Probab. 26, 213–252 (1998)
Marckert, J.-F., Mokkadem, A.: The depth-first processes of Galton-Watson trees converge to the same Brownian excursion. Ann. Probab. 31, 1655–1678 (2003)
Miermont, G.: Ordered additive coalescent and fragmentations associated to Lévy processes with no positive jumps. Electr. J. Probab. 6, paper 14, 33~pp. (2001)
Millar, P.W.: Comparison theorems for sample function growth. Ann. Probab. 9, 330–334 (1981)
O’Cinneide, C.A., Pokrovskii, A.V.: Nonuniform random transformations. Ann. Appl. Probab. 10(4), 1151–1181 (2000)
Pitman, J.: Random mappings, forests and subsets associated with Abel-Cayley-Hurwitz multinomial expansions. Séminaire Lotharingien de Combinatoire, Issue 46, 45~pp., (2001) www.mat.univie.ac.at/~slc/
Pitman, J., Yor, M.: Arcsine laws and interval partitions derived from a stable subordinator. Proc. London Math. Soc. 3 (65), 326–356 (1992)
Revuz, D., Yor, M.: Continuous martingales and Brownian motion. Springer, Berlin-Heidelberg, third edition, 1999
Vervaat, W.: A relation between Brownian bridge and Brownian excursion. Ann. Probab. 7, 143–149 (1979)
Author information
Authors and Affiliations
Additional information
D. Aldous: Research supported in part by N.S.F. Grant DMS-0203062
J. Pitman: Research supported in part by N.S.F. Grant DMS-0071448
Mathematics Subject Classification (2000): 60C05, 60F17, 60G09, 60G51
Rights and permissions
About this article
Cite this article
Aldous, D., Miermont, G. & Pitman, J. The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin’s local time identity. Probab. Theory Relat. Fields 129, 182–218 (2004). https://doi.org/10.1007/s00440-003-0334-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-003-0334-7