The asymptotic distribution of the diameter of a random mapping. (English) Zbl 1002.60075

The authors give an asymptotic distribution of the diameter of the digraph of a uniformly distributed random mapping of an \(n\)-element set to itself as the distribution of a functional of reflecting Brownian bridge. This yields a formula for the Mellin transform of the asymptotic distribution, generalizing the evaluation of its mean by P. Flajolet and A. M. Odlyzko [in: Advances in cryptology – EUROCRYPT ’89. Lect. Notes Comput. Sci. 434, 329-354 (1990; Zbl 0747.05006)]. The methodology should be applicable to other characteristics of random mappings.


60J65 Brownian motion


Zbl 0747.05006
Full Text: DOI


[1] Aldous, D.; Pitman, J., Brownian bridge asymptotics for random mappings, Random structures and algorithms, 5, 487-512, (1994) · Zbl 0811.60057
[2] D. Aldous, J. Pitman, Invariance principles for non-uniform random mappings and trees, Technical Report 594, Dept. Statistics, U.C. Berkeley, 2001. To appear in Asymptotic Combinatorics and Mathematical Physics, Proceedings of NATO Advanced Study Institute, St Petersburg, 2001, V. Malyshev, A. Vershik (Eds.), 2002 · Zbl 1027.60003
[3] Biane, P.; Le Gall, J.F.; Yor, M., Un processus qui ressemble au pont brownien, (), 270-275 · Zbl 0621.60086
[4] Flajolet, P.; Odlyzko, A., Random mapping statistics, (), 329-354 · Zbl 0747.05006
[5] Knuth, D.E., The art of computer programming, 2, (1969), Addison-Wesley · Zbl 0191.18001
[6] Łuckzak, T., Random trees and random graphs, Random structures algorithms, 13, 485-500, (1998)
[7] Perman, M., Order statistics for jumps of normalized subordinators, Stoch. proc. appl., 46, 267-281, (1993) · Zbl 0777.60070
[8] Pitman, J.; Yor, M., Arcsine laws and interval partitions derived from a stable subordinator, Proc. London math. soc. (3), 65, 326-356, (1992) · Zbl 0769.60014
[9] Pitman, J.; Yor, M., The two-parameter poisson – dirichlet distribution derived from a stable subordinator, Ann. probab., 25, 855-900, (1997) · Zbl 0880.60076
[10] Pitman, J.; Yor, M., On the distribution of ranked heights of excursions of a Brownian bridge, Ann. probab., 29, 362-384, (2001) · Zbl 1033.60050
[11] Ye, D.; Dai, Z.; Lam, K.-Y., Decomposing attacks on asymmetric cryptography based on mapping compositions, J. cryptology, 14, 137-150, (2001) · Zbl 1021.94526
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.