Compositions of random functions on a finite set (Q1601113)

Summary: If we compose sufficiently many random functions on a finite set, then the composite function will be constant. We determine the number of compositions that are needed, on average. Choose random functions \(f_1, f_2,f_3,\dots \) independently and uniformly from among the \(n^n\) functions from \([n]\) into \([n]\). For \(t>1\), let \(g_t=f_t\circ f_{t-1}\circ \cdots \circ f_1\) be the composition of the first \(t\) functions. Let \(T\) be the smallest \(t\) for which \(g_t\) is constant (i.e. \(g_t(i)=g_t(j)\) for all \(i,j\)). We prove that \(E(T)\sim 2n\) as \(n\rightarrow\infty\), where \(E(T)\) denotes the expected value of \(T\).