Deje $G$ ser una permutación de grupo en el conjunto finito $\Omega$. Considere la posibilidad de la cadena de Markov donde se comienza con un elemento $\alpha \in \Omega$ elegido de algunos de partida arbitrario de distribución de probabilidad. Un paso en la cadena de Markov implica los siguientes:
- Pasar de $\alpha$ a un elemento aleatorio $g\in G$ que corrige $\alpha$.
- Pasar de $g$ a un elemento aleatorio $\beta\in \Omega$ que es fijado por la $g$.
Ya que es posible pasar de cualquier $\alpha$ cualquier $\beta$ $\Omega$ en un solo paso (a través de la identidad de $G$) de la cadena de Markov es irreducible y aperiódica. Esto implica que no hay una única distribución que es abordado por repitiendo el procedimiento anterior desde el inicio de la distribución. No es difícil mostrar que la limitación de la distribución es aquella en la que todas las órbitas son igualmente probables (es decir, la probabilidad de alcanzar $\alpha$ es inversamente proporcional al tamaño de la órbita que lo contiene).
He leído acerca de esta bonita construcción en el P. J. Cameron "Permutación de Grupos", en donde se plantea lo que él llama un lema de la moderna enumeración teoría: "...la capacidad de contar con un conjunto está estrechamente relacionado con la capacidad de seleccionar un elemento aleatorio a partir de ese conjunto (con todos los elementos igualmente probables)."
Un caso especial de esta cadena de Markov es cuando dejamos $\Omega=G$ y la acción de la conjugación, entonces tenemos una limitación de la distribución, donde todas las clases conjugacy de $G$ son igualmente probables. Ahora, a excepción de este buen resultado, también sería interesante saber algo acerca de la tasa de convergencia de esta cadena. Cameron menciona que es rápidamente mezcla (converge exponencialmente rápido a la limitación de la distribución), en algunos casos importantes, pero los ejemplos donde no rápidamente la mezcla también puede ser construido. Mi pregunta es:
Pregunta: ¿se Puede describir la velocidad de convergencia de la cadena de Markov se describe anteriormente en términos de grupo-conceptos teóricos (propiedades de $G$)?
Mientras se da a la tasa de convergencia en términos de las propiedades de $G$ podría ser una pregunta difícil de contestar, las respuestas con condiciones suficientes para la cadena ser rápidamente mezcla también son bienvenidos.
