Iterating random functions on a finite set

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Let f_1,f_2,..., be functions chosen independently and uniformly from the set of all functions from a set of cardinality n into itself. Let g_t be the composition of the first t functions, and let T be the smallest t for which g_t is constant. We find the limiting distribution of T/n, as n --> infinity.
update references and conjecture's status

Keywords

Combinatorics, Probability, 05A16, 05A05, 60C05, 60J10

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/64610

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0207276
 http://arxiv.org/abs/math/0207276

Collections

arXiv