Random mapping statistics

Abstract : Random mappings from a finite set into itself are either a heuristic or an exact model for a variety of applications in random number generation, computational number theory, cryptography, and the analysis of algorithms at large. This paper introduces a general framework in which the analysis of about twenty characteristic parameters of random mappings is carried out. These parameters are studied systematically through the use of generating functions and singularity analysis. In particular, an open problem of Knuth is solved, namely that of finding the expected diameter of a random mapping. The same approach is applicable to a larger class of discrete combinatorial models and possibilities of automated analysis using symbolic manipulation systems ("computer algebra") are also briefly discussed.
Type de document :
Rapport
[Research Report] RR-1114, INRIA. 1989
Liste complète des métadonnées

https://hal.inria.fr/inria-00075445
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:13:54
Dernière modification le : vendredi 16 septembre 2016 - 15:11:38
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:02:45

Fichiers

Identifiants

  • HAL Id : inria-00075445, version 1

Collections

Citation

Philippe Flajolet, Andrew M. Odlyzko. Random mapping statistics. [Research Report] RR-1114, INRIA. 1989. <inria-00075445>

Partager

Métriques

Consultations de
la notice

133

Téléchargements du document

716