The asymptotic distribution of the diameter of a random mapping
[La loi limite du diamètre d'une application aléatoire]
Aldous, David1 ; Pitman, Jim1
1 Department of Statistics, University of California, 367 Evans Hall # 3860, Berkeley, CA 94720-3860, USA
Comptes Rendus. Mathématique, Tome 334 (2002) no. 11, pp. 1021-1024.

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.

Reçu le :
Révisé le :
Publié le :
DOI : 10.1016/S1631-073X(02)02386-5
Aldous, David 1 ; Pitman, Jim 1

1 Department of Statistics, University of California, 367 Evans Hall # 3860, Berkeley, CA 94720-3860, USA 
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1016/S1631-073X(02)02386-5/

[1] Aldous, D.; Pitman, J. 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] Biane, P.; Le Gall, J.F.; Yor, M. Un processus qui ressemble au pont brownien, Séminaire de Probabilités XXI, Lecture Notes in Math., 1247, Springer, 1987, pp. 270-275

[4] Flajolet, P.; Odlyzko, A. 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] Knuth, D.E., The Art of Computer Programming, 2, Addison-Wesley, 1969

[6] Łuckzak, T. Random trees and random graphs, Random Structures Algorithms, Volume 13 (1998), pp. 485-500

[7] Perman, M. Order statistics for jumps of normalized subordinators, Stoch. Proc. Appl., Volume 46 (1993), pp. 267-281

[8] Pitman, J.; Yor, M. Arcsine laws and interval partitions derived from a stable subordinator, Proc. London Math. Soc. (3), Volume 65 (1992), pp. 326-356

[9] Pitman, J.; Yor, M. The two-parameter Poisson–Dirichlet distribution derived from a stable subordinator, Ann. Probab., Volume 25 (1997), pp. 855-900

[10] Pitman, J.; Yor, M. On the distribution of ranked heights of excursions of a Brownian bridge, Ann. Probab., Volume 29 (2001), pp. 362-384

[11] Ye, D.; Dai, Z.; Lam, K.-Y. 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.