This is somewhat inspired by [Factoring a function from a finite set to itself](https://mathoverflow.net/questions/408116/factoring-a-function-from-a-finite-set-to-itself).


Fix natural number $n$ and let $[n] := \{1,2,\ldots,n\}$. Set $g\_0 \colon [n]\to [n]$ to be the identity, and for $i \geq 1$ define $g\_i := f\_i \circ g\_{i-1}$ where the $f\_i\colon [n] \to [n]$ are chosen (independently and) uniformly at random among all functions from $[n]$ to $[n]$.


What is the expected value of the smallest $t$ for which $g\_t$ is a constant function? (More generally, what is the distribution of this random variable $t$?)


**EDIT**: As Peter Taylor explained, it is easy to view this also as a Markov chain on $[n]$ where at time $t$ our state $a\_t$ is the size of the image of $g\_t$. And as I mentioned in the comments then the trajectory of this Markov chain $(a\_1-1,a\_2-1,\ldots)$ gives a random partition with part sizes $\leq n-1$; the expected time to a constant function is the expected length of this partition.


There is also a natural $q$-analog of this problem, where instead of random functions $[n]\to [n]$ we look at random linear functions $\mathbb{F}\_q^n\to \mathbb{F}\_q^n$. This gives a Markov chain on $\{0,1,\ldots,n\}$ where our state $a\_t$ is the dimension of the image of $g\_t$. Of course now the transition probabilities of the Markov chain involve the parameter $q$ (and should recover the previous case with $q=1$).



Expected number of compositions needed to get constant function
This question was completely settled by J.A. Fill here:
<https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.641>


