×

Brownian bridge asymptotics for random mappings. (English) Zbl 0811.60057

This paper deals with the uniform model of random mappings of an \(n\)- element set into itself. The authors introduce a new technique, which starts by specifying a coding of mappings as walks with \(\pm 1\) steps. Then, the uniform random mapping model is thereby coded as a nonuniform random walk. The main result of the paper shows that as \(n\to\infty\) the random walk rescales to reflecting Brownian bridge. This enables to obtain a large number of limiting distributions concerning numerical characteristics of the random digraphs representing random mappings.

MSC:

60G50 Sums of independent random variables; random walks
60J65 Brownian motion
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldous, Lecture Notes in Mathematics 1117, in: École d’Été St. Flour 1983 pp 1– (1985)
[2] Aldous, Stochastic Analysis pp 23– (1991)
[3] Aldous, The continuum random tree III, Ann. Probab. 21 pp 248– (1983)
[4] D. J. Aldous J. Pitman Distributional aspects of a recursive decomposition of Brownian bridge and random mapping asymptotics, in preparation 1994
[5] Bagaev, Limit distributions of metric characteristics of an indecomposable random mapping, Combin. Asymp. Anal. Krasnojarsk. Gos. Univ. 2 pp 55– (1977)
[6] Bertoin, Path transformations connecting Brownian bridge, excursion and meander, Bull. Sci. Math. (1994) · Zbl 0805.60076
[7] Bhattacharaya, Stochastic Processes with Applications (1990)
[8] Billingsley, Convergence of Probability Measures (1968)
[9] Chung, Excursions in Brownian motion, Ark. Mat. 14 pp 155– (1976) · Zbl 0356.60033
[10] Ethier, Markov Processes: Characterization and Convergence (1986)
[11] Flajolet, Lecture Notes in Computer Science 434, in: Advances in Cryptology-EUROCRYPT ’89 pp 329– (1990)
[12] D. Foata La Série Génératrice Exponentielle dans les Problèmes d’Enumération 1974
[13] Graf, The exact Hausdorff dimension in random recursive constructions, Mem. Am. Math. Soc. 71 (381) pp 1– (1988)
[14] Hansen, A functional central limit theorem for random mappings, Ann. Probab. 17 pp 317– (1989) · Zbl 0667.60009
[15] Ann. Probab. 19 pp 1393– (1991)
[16] Ibragimov, Independent and Stationary Sequences of Random Variables (1971)
[17] Imhof, On Brownian bridge and excursion, Stud. Sci. Math. Hung. 20 pp 1– (1985) · Zbl 0625.60096
[18] Itǒ, Diffusion Processes and Their Sample Paths (1965)
[19] Johnson, An explicit formula for the c.d.f. of the L1 norm of the Brownian bridge, Ann. Probab. 11 pp 807– (1983) · Zbl 0516.60044
[20] Kallenberg, Canonical representations and convergence criteria for processes with interchangeable increments, Z. Wahrsch. Verw. Gebiete 27 pp 23– (1973) · Zbl 0253.60060
[21] Knight, Essentials of Brownian Motion and Diffusion RI (1981)
[22] Kolchin, Random Mappings (1986)
[23] Lévy, Sur certains processus stochastiques homogènes, Comp. Math. 7 pp 283– (1939) · JFM 65.1346.02
[24] L. Mutafciev Probability distributions and asymptotics for some characteristics of radom mappings 1983 227 238
[25] L. Mutafciev On some stochastic problems of discrete mathematics Mathematics and Education: Proc. 13th Spring Conf. Bulgarian Mathematicians 1984 57 80
[26] Perman, Order statistics for jumps of normalized subordinators, Stoch. Proc. Appl. 46 pp 267– (1993) · Zbl 0777.60070
[27] Perman, Size-biased sampling of Poisson point processes and excursions, Probab. Theor. Rel. Fields 92 pp 21– (1992) · Zbl 0741.60037
[28] J. Pitman Distribution of local times of Brownian bridge, unpublished 1991 · Zbl 0945.60081
[29] Proskurin, On the distribution of the number of vertices in strata of a random mapping, Theory Probab. Appl. 18 pp 803– (1973) · Zbl 0324.60009
[30] Revuz, Continuous Martingales and Brownian Motion (1991)
[31] Salisbury, Construction of right processes from excursions, Z. Wahrsch. Verw. Gebiete 73 pp 351– (1986) · Zbl 0587.60068
[32] Stepanov, Limit distributions of certain characteristics of random mappings, Theory Probab. Appl. 14 pp 612– (1969)
[33] Stepanov, Random mappings with a single attracting center, Theory Probab. Appl. 16 pp 155– (1971) · Zbl 0239.60017
[34] Takacs, Random walk processes and their application in order statistics, Ann. Appl. Probab. 2 pp 435– (1992)
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.