# Expected number of compositions needed to get constant function

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$$).

• We could even consider the distribution of the random partition $(a_1,a_2,\ldots)$ where $a_i$ is the cardinality of the image of $g_i$ minus one. Dec 1 '21 at 14:13
• Empirically, based on calculations up to $n=99$, it seems to be roughly $1.99n - 2.48$. Dec 1 '21 at 15:02
• @PeterTaylor: it would be very interesting if the leading term were $2n$... Dec 1 '21 at 16:17
• See this paper of Fill: citeseerx.ist.psu.edu/viewdoc/…
– esg
Dec 1 '21 at 18:59
• @SophieMacDonald: For $k=1$ in your set-up, the worst-case expectation will be less than $2n$: because the only singletons allowed correspond to arboresences, whose longest paths must be $< n$ in length. (Incidentally it is a classical fact that the probability a random map $[n]\to [n]$ is eventually constant under self-composition is $1/n$: this is equivalent to Cayley's formula for the number of labeled trees on $[n]$. There is also a beautiful $q$-analog of this: doi.org/10.1080/00029890.2021.1868384) Dec 2 '21 at 19:37

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

• In particular, the belief that the expected value is $(2+o(1))n$ is correct and was in fact proved earlier by Dalal and Schmutz (doi.org/10.37236/1642). I do wonder if the natural $q$-analog of this question has been looked into as well... Dec 1 '21 at 19:14
• In this paper, the result is claimed to be folklore: arxiv.org/abs/math/0207276 Dec 1 '21 at 19:35
• Indeed, most of these results had already been obtained (in a slightly different guise) by J.F.C. Kingman in 1982, see inference.org.uk/sustainable/… . A generalization to more general distributions was given in arxiv.org/pdf/0809.4233.pdf
– esg
Dec 3 '21 at 17:32

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$$.

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.