Random mapping statistics - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1989

Random mapping statistics

Philippe Flajolet
  • Fonction : Auteur
  • PersonId : 829512
Andrew M. Odlyzko
  • Fonction : Auteur

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1114.pdf (1.56 Mo) Télécharger le fichier

Dates et versions

inria-00075445 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00075445 , version 1

Citer

Philippe Flajolet, Andrew M. Odlyzko. Random mapping statistics. [Research Report] RR-1114, INRIA. 1989. ⟨inria-00075445⟩
809 Consultations
2107 Téléchargements

Partager

Gmail Facebook X LinkedIn More