Supongo que la respuesta es $(2+o(1))n$ .
Como dice Peter Taylor: Tenemos un proceso de Markov en el conjunto $[n]:=\{ 1,2, \ldots, n \}$ donde la probabilidad de transición de $i \to j$ es la probabilidad de que una función elegida al azar de entre $[i] \to [n]$ tendrá una imagen de tamaño $j$ . Arreglar algunos $m \geq 2$ y considerar la ejecución de este proceso de Markov a partir de $m$ . Demostraré que el tiempo previsto para alcanzar $1$ es $(2-2/m+o(1)) n$ .
Para $k$ fija, la probabilidad de la transición $k \to k$ es $1-\binom{k}{2} \tfrac{1}{n} + O(1/n^2)$ la probabilidad de una transición $k \to k-1$ es $\binom{k}{2} \tfrac{1}{n} + O(1/n^2)$ y la probabilidad de una transición $k \to \ell$ para $\ell \leq k-2$ es $O(1/n^2)$ .
Consideremos el proceso simplificado en el que la probabilidad de transición $k \to k$ es $1-\binom{k}{2} \tfrac{1}{n}$ la probabilidad de $k \to k-1$ es $\binom{k}{2} \tfrac{1}{n}$ y la probabilidad de $k \to \ell$ para $\ell \leq k-2$ es $0$ . El tiempo previsto para que este proceso pase de $k$ a $k-1$ es $\tfrac{2n}{k(k-1)}$ por lo que el tiempo previsto para pasar de $m$ a $1$ es $2n \sum_{k=2}^m \tfrac{1}{k(k-1)} = 2n (1-1/m)$ . Podemos pensar en el proceso original como la aplicación del proceso simplificado, y luego cambiar de opinión con probabilidad $O(1/n^2)$ en cada paso. Pero como sólo tomamos $O(n)$ pasos, la probabilidad de que alguna vez cambiemos de opinión es $O(1/n)$ por lo que tenemos el mismo tiempo previsto para el proceso original que para el proceso simplificado. (Me estoy saltando algunos detalles, pero estoy bastante seguro de poder completarlos).
Ahora, es tentador enviar $m \to \infty$ y concluir que el tiempo esperado desde $n$ a $1$ es $(2+o(1))n$ . Creo que deberías ser capaz de demostrar rigurosamente un límite inferior por esta vía sin esforzarte demasiado. Quiero proporcionar argumentos no rigurosos que $2$ es la constante correcta.
Fijar $\beta$ en $[1, \infty)$ y supongamos que el proceso de Markov se encuentra en la posición $n/\beta$ . La probabilidad de que un elemento fijo en $[n]$ está en la imagen de un mapa aleatorio $[n/\beta] \to [n]$ es $1-(1-1/n)^{n/\beta} \approx 1-e^{-\beta^{-1}}$ . Así, a grandes rasgos, el proceso de Markov va de $\alpha n$ a $(1-e^{-\beta^{-1}})n=n/(1-e^{-\beta^{-1}})^{-1}$ . La iteración $\beta \mapsto (1-e^{-\beta^{-1}})^{-1}$ se acerca a $\infty$ . Por lo tanto, si fijamos $R>0$ espero que el proceso de Markov sea inferior a $n/R$ en un número finito de pasos.
Ahora, ¿cuánto tiempo debo esperar la transición de $n/R$ a $n/S$ ser, si $R < S$ son fijos y grandes? Tenemos $$(1-e^{-\beta^{-1}})^{-1} = \beta + 1/2 + O(\beta^{-1}) \ \text{as}\ \beta \to \infty.$$ Esto sugiere que el tiempo para pasar de $\beta = R$ a $\beta=S$ es aproximadamente $2(S-R)$ . Envío de $S \to n$ sugiere que la respuesta a la pregunta original debería ser $(2+o(1))n$ . (Aquí no estoy nada seguro de poder completar los detalles).
En realidad no he dado una prueba, pero he analizado tanto la parte de la cadena de Markov donde $k = O(1)$ y la parte en la que $k \sim n$ y se obtuvieron resultados coherentes.
