Expected number of compositions needed to get constant function

Question

This is somewhat inspired by 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$).

Answer 1

This question was completely settled by J.A. Fill here: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.641

Answer 2

We have a Markov process where the state after $i$ steps is given by the size of the codomain of $g_i$. If at time $i$ we are in a state with $j$ surviving values, we can ignore the other values and consider $f_{i+1}$ as a function from the codomain of $g_{i}$ to $[n]$. Then the probability of a transition to state $k$ is given by $\binom{n}{k} \{{j \atop k}\} k! \, n^{-j}$ and we can calculate the expected hitting time from state $j$ as $$\tau_j = \begin{cases} 0 & \textrm{if } j = 1 \\ \frac{1 + \sum_{k=1}^{j-1} \binom{n}{k} \{{j \atop k}\} k!\, n^{-j} \tau_k }{1 - \binom{n}{j} j!\, n^{-j}} & \textrm{otherwise} \end{cases}$$

Cancellation gives the marginally simpler expression $$\tau_j = \frac{n^j + n! \sum_{k=1}^{j-1} \{{j \atop k}\} \frac{\tau_k}{(n-k)!} }{n^j - n!/(n-j)!}$$ for $j > 1$.

Answer 3

I expect the answer is $(2+o(1))n$.

---

As Peter Taylor says: We have a Markov process on the set $[n]:=\{ 1,2, \ldots, n \}$ where the transition probability from $i \to j$ is the probability that a randomly selected function from $[i] \to [n]$ will have image of size $j$. Fix some $m \geq 2$ and consider running this Markov process starting at $m$. I will show that the expected time to reach $1$ is $(2-2/m+o(1)) n$.

For $k$ fixed, the probability of the transition $k \to k$ is $1-\binom{k}{2} \tfrac{1}{n} + O(1/n^2)$, the probability of a transition $k \to k-1$ is $\binom{k}{2} \tfrac{1}{n} + O(1/n^2)$ and the probability of a transition $k \to \ell$ for $\ell \leq k-2$ is $O(1/n^2)$.

Consider the simplified process where the probability of transitioning $k \to k$ is $1-\binom{k}{2} \tfrac{1}{n}$, the probability of $k \to k-1$ is $\binom{k}{2} \tfrac{1}{n}$ and the probability of $k \to \ell$ for $\ell \leq k-2$ is $0$. The expected time for this process to go from $k$ to $k-1$ is $\tfrac{2n}{k(k-1)}$ so the expected time to go from $m$ to $1$ is $2n \sum_{k=2}^m \tfrac{1}{k(k-1)} = 2n (1-1/m)$. We can think of the original process as applying the simplified process, and then changing our mind with probability $O(1/n^2)$ at each step. But since we only take $O(n)$ steps, the probability that we ever change our mind is $O(1/n)$, so we have the same expected time for the original process as for the simplified process. (I am skipping over some details, but I'm pretty sure I can fill them in.)

---

Now, it is tempting to send $m \to \infty$ and conclude that the expected time from $n$ to $1$ is $(2+o(1))n$. I think you should be able to rigorously prove a lower bound by this route without working too hard. I want to provide nonrigourous arguments that $2$ actualy is the right constant.

Fix $\beta$ in $[1, \infty)$ and suppose the Markov process is at position $n/\beta$. The probability that a fixed element in $[n]$ is in the image of a random map $[n/\beta] \to [n]$ is $1-(1-1/n)^{n/\beta} \approx 1-e^{-\beta^{-1}}$. So, roughly, the Markov process goes from $\alpha n$ to $(1-e^{-\beta^{-1}})n=n/(1-e^{-\beta^{-1}})^{-1}$. The iteration $\beta \mapsto (1-e^{-\beta^{-1}})^{-1}$ approaches $\infty$. So, if we fix some $R>0$, I expect the Markov process to get below $n/R$ in a finite number of steps.

Now, how long should I expect the transition from $n/R$ to $n/S$ to be, if $R < S$ are fixed and large? We have $$(1-e^{-\beta^{-1}})^{-1} = \beta + 1/2 + O(\beta^{-1}) \ \text{as}\ \beta \to \infty.$$ This suggests that the time to go from $\beta = R$ to $\beta=S$ is roughly $2(S-R)$. Sending $S \to n$ suggests the answer to the original question should be $(2+o(1))n$. (Here I am not at all sure I can fill in the details.)

---

I haven't actually given a proof, but I've analyzed both the part of the Markov chain where $k = O(1)$, and the part where $k \sim n$, and found consistent results.