Skip to main content
2 of 3
added 13 characters in body
David E Speyer
  • 156.4k
  • 14
  • 422
  • 763

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 modified process. (I am skipping over some details.)


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 $2(S-R)$. Sending $S \to n$ suggests the answer to the original question should be $(2+o(1))n$.


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.

David E Speyer
  • 156.4k
  • 14
  • 422
  • 763