A partir de una permutación de la identidad P = [1,2,3,4,5], cada paso elija dos números aleatorios enteros k y l en [1,5]. Luego intercambiar P [k] y P [l]. Detener el proceso hasta que P se convierte otra vez identidad. Observar que el número esperado de pasos es de 120. Yo no puedo comprobarlo teóricamente. Por favor, guíame.
Respuesta
¿Demasiados anuncios?
La elección de dos valores al azar y el intercambio de ellos crea una doblemente estocástico de cadenas de Markov en el espacio $\cal S$ de todas las permutaciones. El único invariante de la distribución de probabilidad es uniforme en este espacio, y (por la cadena de Markov teoría) el número esperado de pasos para volver a la posición original es el recíproco de la masa en ese estado: es decir, $\mathbb{E}_e(T_e)=1/\pi(e)=|{\cal S}|=120$.
En mi respuesta a esta pregunta, voy a resolver otro problema con el mismo método, y tratar de explicar el resultado de una forma intuitiva.
