Pregunta sobre el valor esperado de las biyecciones de $\{1,2,\ldots,n\}$ .

Question

Contexto: esto es sólo un problema que se me ocurrió por diversión.

Dejemos que $\Sigma_n$ sea el grupo simétrico en $\{1,2,\ldots n\}$ . Definimos una variable aleatoria $X$ en $\Sigma_n$ por:

$$X(f)=\mbox{max}\{k\mid\forall j\leq k, f(j)\geq j\}.$$

En otras palabras, $X(f)$ es el mayor $k$ tal que, en el gráfico de $f$ los puntos $(1,f(1))$ , $(2,f(2))$ , $\cdots$ , $(k,f(k))$ todos se encuentran en o por encima de la diagonal. Mi pregunta es: ¿Qué es $E[X]$ ? ¿Existe siquiera una forma "agradable" de encontrarlo o expresarlo? Si no es así, ¿hay alguna forma de estimar $E[X]$ ?

Answer 1

Claro, utiliza la fórmula $$\mathbb E[X] = \sum_{k \ge 1} \Pr[X \ge k].$$ Para un fijo $k$ , $X \ge k$ si y sólo si $f(j) \ge j$ para todos $j \le k$ . Hay $(n-k+1)^k \cdot (n-k)!$ permutaciones $f$ que satisfagan esto:

• Podemos elegir $f(k) \in \{k, k+1, k+2, \dots, n\}$ en $n-k+1$ formas.
• Una vez hecho esto, podemos elegir $f(k-1) \in \{k-1, k, k+1, \dots, n\} \setminus \{f(k)\}$ en $n-k+1$ formas.
• Trabajando hacia atrás, tenemos $n-k+1$ opciones para cada uno de $f(k-2), f(k-3), \dots, f(1)$ .
• Por último, no nos importa lo que $f(k+1), \dots, f(n)$ son, pero hay $(n-k)!$ formas de organizarlas al final.

Esto nos da $$\mathbb E[X] = \sum_{k=1}^n \frac{(n-k+1)^k\,(n-k)!}{n!}$$ que no parece simplificar bien, pero probablemente se puede argumentar que es $\mathcal O(\sqrt n)$ basado en el hecho de que el $k^{\text{th}}$ término es aproximadamente $1$ cuando $k \ll \sqrt n$ y muy cerca de $0$ cuando $k \gg \sqrt n$ .