Brownian Bridge Asymptotics for Random $p$-Mappings

David Aldous (University of California, Berkeley)
Gregory Miermont (Ecole Normale Superieure)
Jim Pitman (University of California, Berkeley)

Abstract


The Joyal bijection between doubly-rooted trees and mappings can be lifted to a transformation on function space which takes tree-walks to mapping-walks. Applying known results on weak convergence of random tree walks to Brownian excursion, we give a conceptually simpler rederivation of the Aldous-Pitman (1994) result on convergence of uniform random mapping walks to reflecting Brownian bridge, and extend this result to random $p$-mappings.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 37-56

Publication Date: February 13, 2004

DOI: 10.1214/EJP.v9-186

References

    Aldous, David ; Pitman, Jim. Two recursive decompositions of Brownian bridge related to the asymptotics of random mappings. Technical Report 595, Dept. Statistics, U.C. Berkeley, 2002.
    Aldous, David. The continuum random tree. III. Ann. Probab. 21 (1993), no. 1, 248--289. MR1207226
    Aldous, David ; Miermont, Gregory; Pitman, Jim. Weak convergence of random p-mappings and the exploration process of the inhomogeneous continuum random tree. In preparation, 2004.
    Aldous, David ; Pitman, Jim. Brownian bridge asymptotics for random mappings. Random Structures Algorithms 5 (1994), no. 4, 487--512. MR1293075
    Aldous, David; Pitman, Jim. The asymptotic distribution of the diameter of a random mapping. C. R. Math. Acad. Sci. Paris 334 (2002), no. 11, 1021--1024. MR1913728
    Aldous, David; Pitman, Jim. Invariance principles for non-uniform random mappings and trees. Asymptotic combinatorics with application to mathematical physics (St. Petersburg, 2001), 113--147, NATO Sci. Ser. II Math. Phys. Chem., 77, Kluwer Acad. Publ., Dordrecht, 2002. MR1999358
    Bertoin, Jean; Pitman, Jim. Path transformations connecting Brownian bridge, excursion and meander. Bull. Sci. Math. 118 (1994), no. 2, 147--166. MR1268525
    Biane, Ph. Relations entre pont et excursion du mouvement brownien rÈel. Ann. Inst. H. PoincarÈ Probab. Statist. 22 (1986), no. 1, 1--7. MR0838369
    Biane, Philippe. Some comments on the paper: "Brownian bridge asymptotics for random mappings" [Random Structures Algorithms 5 (1994), no. 4, 487--512 MR95k:60055 ] by D. J. Aldous and J. W. Pitman. Random Structures Algorithms 5 (1994), no. 4, 513--516. MR1293076
    Camarri, Michael; Pitman, Jim. Limit distributions and random trees derived from the birthday problem with unequal probabilities. Electron. J. Probab. 5 (2000), no. 1, 18 pp. (electronic). MR1741774
    Drmota, Michael; Gittenberger, Bernhard. On the profile of random trees. Random Structures Algorithms 10 (1997), no. 4, 421--451. MR1608230
    Harris, B. A survey of the early history of the theory of random mappings. Probabilistic methods in discrete mathematics (Petrozavodsk, 1992), 1--22, Progr. Pure Appl. Discrete Math., 1, VSP, Utrecht, 1993. MR1383124
    Joyal, AndrÈ. Une thÈorie combinatoire des sÈries formelles. (French) [A combinatorial theory of formal series] Adv. in Math. 42 (1981), no. 1, 1--82. MR0633783
    Kolchin, Valentin F. Random mappings. Translated from the Russian. With a foreword by S. R. S. Varadhan. Translation Series in Mathematics and Engineering. Optimization Software, Inc., Publications Division, New York, 1986. xiv + 207 pp. ISBN: 0-911575-16-2 MR0865130
    Marckert, Jean-FranÁois; Mokkadem, Abdelkader. The depth first processes of Galton-Watson trees converge to the same Brownian excursion. Ann. Probab. 31 (2003), no. 3, 1655--1678. MR1989446
    O'Cinneide, C. A.; Pokrovskii, A. V. Nonuniform random transformations. Ann. Appl. Probab. 10 (2000), no. 4, 1151--1181. MR1810869
    Pitman, Jim. Random mappings, forests, and subsets associated with Abel-Cayley-Hurwitz multinomial expansions. Sém. Lothar. Combin. 46 (2001/02), Art. B46h, 45 pp. (electronic). MR1877634
    Pitman, Jim. Combinatorial Stochastic Processes. Technical Report 621, Dept. Statistics, U.C. Berkeley, 2002. Lecture notes for St. Flour course, July 2002.
    Pitman, Jim; Yor, Marc. Arcsine laws and interval partitions derived from a stable subordinator. Proc. London Math. Soc. (3) 65 (1992), no. 2, 326--356. MR1168191
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.