Supongamos que tenemos $n$ elementos en una permutación aleatoria (cada permutación tiene igual probabilidad inicialmente). Mientras los elementos no estén completamente ordenados, intercambiamos dos elementos adyacentes al azar (por ejemplo, la permutación $(1, 3, 2)$ puede ir a $(1, 2, 3)$ o $(3, 1, 2)$ con una probabilidad igual de $0.5$). ¿Cuántas veces se necesita en promedio para ordenar completamente los $n$ elementos?
Para el caso $n=2$, hay una probabilidad de $0.5$ de que los elementos ya estén ordenados, en cuyo caso no se necesitan intercambios, y una probabilidad de $0.5$ de que los dos elementos se intercambien, en cuyo caso se necesita un solo intercambio para ordenar los elementos, por lo que en promedio se necesitan $0.5$ intercambios.
Para el caso $n=3$, utilicé una cadena de Markov para representar las posibles permutaciones, y (sin entrar en detalles) encontré que en promedio se necesitarían $5\frac{5}{6}$ intercambios para ordenar los $3$ elementos.
Para $n\geq4$ es demasiado difícil construir manualmente cadenas de Markov que representen las permutaciones, pero noté:
- El número de inversiones siempre cambia exactamente $1$
- Desde cualquier estado dado, hay $n-1$ posibles estados a los que puedes transicionar
¿Alguna idea para obtener una forma cerrada del número esperado de intercambios?
