Comptes Rendus
no. 11
The asymptotic distribution of the diameter of a random mapping
[La loi limite du diamètre d'une application aléatoire]
David Aldous1 ; Jim Pitman1
1 Department of Statistics, University of California, 367 Evans Hall # 3860, Berkeley, CA 94720-3860, USA
Comptes Rendus. Mathématique, Volume 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

David Aldous 1 ; Jim Pitman 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 = {David Aldous and Jim Pitman},
     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},
}
TY  - JOUR
AU  - David Aldous
AU  - Jim Pitman
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
DO  - 10.1016/S1631-073X(02)02386-5
LA  - en
ID  - CRMATH_2002__334_11_1021_0
ER  - 
%0 Journal Article
%A David Aldous
%A Jim Pitman
%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
%R 10.1016/S1631-073X(02)02386-5
%G en
%F CRMATH_2002__334_11_1021_0
David Aldous; Jim Pitman. The asymptotic distribution of the diameter of a random mapping. Comptes Rendus. Mathématique, Volume 334 (2002) no. 11, pp. 1021-1024. doi : 10.1016/S1631-073X(02)02386-5. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(02)02386-5/

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

[4] P. Flajolet; A. Odlyzko Random mapping statistics (J.-J. Quisquater; J. Vandewalle, eds.), Advances in Cryptology – EUROCRYPT '89, Lecture Notes in Comput. Sci., 434, Springer-Verlag, 1990, pp. 329-354

[5] D.E. Knuth, The Art of Computer Programming, 2, Addison-Wesley, 1969

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

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

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

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

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

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

Commentaires - Politique