12
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Dec 1, 2021 at 14:13
  • 2
    $\begingroup$ Empirically, based on calculations up to $n=99$, it seems to be roughly $1.99n - 2.48$. $\endgroup$ Dec 1, 2021 at 15:02
  • 1
    $\begingroup$ @PeterTaylor: it would be very interesting if the leading term were $2n$... $\endgroup$ Dec 1, 2021 at 16:17
  • 1
    $\begingroup$ See this paper of Fill: citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – esg
    Dec 1, 2021 at 18:59
  • 1
    $\begingroup$ @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) $\endgroup$ Dec 2, 2021 at 19:37

3 Answers 3

5
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$ Dec 1, 2021 at 19:14
  • $\begingroup$ In this paper, the result is claimed to be folklore: arxiv.org/abs/math/0207276 $\endgroup$ Dec 1, 2021 at 19:35
  • 1
    $\begingroup$ 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 $\endgroup$
    – esg
    Dec 3, 2021 at 17:32
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.