[La loi limite du diamètre d'une application aléatoire]
On exprime la loi limite du diamètre du digraphe d'une application aléatoire, choisie uniformément parmi les applications d'un ensemble à n éléments dans lui-même, comme la loi d'une fonctionnelle du pont brownien réfléchi. Ceci donne une formule pour la transformée de Mellin de cette loi limite, généralisant la formule pour sa moyenne due a Flajolet et Odlyzko (1990). Cette méthodologie devrait pouvoir s'appliquer a d'autres caractéristiques des applications aléatoires.
The asymptotic distribution of the diameter of the digraph of a uniformly distributed random mapping of an n-element set to itself is represented as the distribution of a functional of a reflecting Brownian bridge. This yields a formula for the Mellin transform of the asymptotic distribution, generalizing the evaluation of its mean by Flajolet and Odlyzko (1990). The methodology should be applicable to other characteristics of random mappings.
Révisé le :
Publié le :
@article{CRMATH_2002__334_11_1021_0,
author = {Aldous, David and Pitman, Jim},
title = {The asymptotic distribution of the diameter of a random mapping},
journal = {Comptes Rendus. Math\'ematique},
pages = {1021--1024},
publisher = {Elsevier},
volume = {334},
number = {11},
year = {2002},
doi = {10.1016/S1631-073X(02)02386-5},
language = {en},
url = {http://www.numdam.org/articles/10.1016/S1631-073X(02)02386-5/}
}
TY - JOUR AU - Aldous, David AU - Pitman, Jim TI - The asymptotic distribution of the diameter of a random mapping JO - Comptes Rendus. Mathématique PY - 2002 SP - 1021 EP - 1024 VL - 334 IS - 11 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/S1631-073X(02)02386-5/ DO - 10.1016/S1631-073X(02)02386-5 LA - en ID - CRMATH_2002__334_11_1021_0 ER -
%0 Journal Article %A Aldous, David %A Pitman, Jim %T The asymptotic distribution of the diameter of a random mapping %J Comptes Rendus. Mathématique %D 2002 %P 1021-1024 %V 334 %N 11 %I Elsevier %U http://www.numdam.org/articles/10.1016/S1631-073X(02)02386-5/ %R 10.1016/S1631-073X(02)02386-5 %G en %F CRMATH_2002__334_11_1021_0
Aldous, David; Pitman, Jim. The asymptotic distribution of the diameter of a random mapping. Comptes Rendus. Mathématique, Tome 334 (2002) no. 11, pp. 1021-1024. doi : 10.1016/S1631-073X(02)02386-5. http://www.numdam.org/articles/10.1016/S1631-073X(02)02386-5/
[1] Brownian bridge asymptotics for random mappings, Random Structures and Algorithms, Volume 5 (1994), pp. 487-512
[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
[3] Un processus qui ressemble au pont brownien, Séminaire de Probabilités XXI, Lecture Notes in Math., 1247, Springer, 1987, pp. 270-275
[4] Random mapping statistics (Quisquater, J.-J.; Vandewalle, J., eds.), Advances in Cryptology – EUROCRYPT '89, Lecture Notes in Comput. Sci., 434, Springer-Verlag, 1990, pp. 329-354
[5] , The Art of Computer Programming, 2, Addison-Wesley, 1969
[6] Random trees and random graphs, Random Structures Algorithms, Volume 13 (1998), pp. 485-500
[7] Order statistics for jumps of normalized subordinators, Stoch. Proc. Appl., Volume 46 (1993), pp. 267-281
[8] Arcsine laws and interval partitions derived from a stable subordinator, Proc. London Math. Soc. (3), Volume 65 (1992), pp. 326-356
[9] The two-parameter Poisson–Dirichlet distribution derived from a stable subordinator, Ann. Probab., Volume 25 (1997), pp. 855-900
[10] On the distribution of ranked heights of excursions of a Brownian bridge, Ann. Probab., Volume 29 (2001), pp. 362-384
[11] Decomposing attacks on asymmetric cryptography based on mapping compositions, J. Cryptology, Volume 14 (2001), pp. 137-150
Cité par Sources :
☆ Research supported in part by N.S.F. Grants DMS-9970901 and DMS-0071448.
