Iterating random functions on a finite set
From MaRDI portal
Publication:6472011
arXivmath/0207276MaRDI QIDQ6472011FDOQ6472011
Authors: William M. Y. Goh, Paweł Hitczenko, Eric Schmutz 
Publication date: 29 July 2002
Abstract: 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.
Permutations, words, matrices (05A05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Asymptotic enumeration (05A16)
This page was built for publication: Iterating random functions on a finite set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6472011)
