Paseos aleatorios en grupos simétricos

En general, para un proceso de Markov irreducible y aperiódico en un espacio de estado finito, el tiempo de retorno esperado a un estado$x$es siempre el recíproco de la única probabilidad de estado estacionario para$x$. Para ver esto, deja$T_0,T_1,T_2,\dots$ser los tiempos de regreso a$x$cuando el proceso de Markov comienza en$x$, donde definimos$T_0=0$. Tenga en cuenta que

$${T_n\over n}=\frac1n\left[(T_1-T_0)+(T_2-T_1)+\dots+(T_n-T_{n-1})\right]$$ Por la ley fuerte de los grandes números,$T_n/n\to E[T_1]$, el tiempo esperado de regreso a$x$. Por otro lado,$n/T_n$es la proporción de visitas a$x$entre los primeros$T_n$pasos del proceso, ya que había exactamente$n$visitas Dado que asumimos que el proceso converge a un único vector de estado estacionario, también debemos tener$n/T_n\to p_{\infty}(x)$.

Tu paseo al azar en$S_n$es irreducible y aperiódica. Dado que la simetría implica que la probabilidad de estado estacionario para todos los elementos del grupo es igual, debe ser$1/n!$para cada uno, por lo que el tiempo de retorno esperado para todos los elementos es$n!$.