![](images/spacer.gif) |
|
|
| | | | | |
|
|
|
|
|
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: PDF
Pages: 37-56
Published on: February 13, 2004
|
Bibliography
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
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|