Iterating random functions on a finite set

الأصل · EN

Let f₁,f₂,..., be functions chosen independently and uniformly from the set of all functions from a set of cardinality n into itself. Let gₜ be the composition of the first t functions, and let T be the smallest t for which gₜ is constant. We find the limiting distribution of T/n, as n --> infinity.