Let $G$ be a permutation group on the finite set $\Omega$. Consider the Markov chain where you start with an element $\alpha \in \Omega$ chosen from some arbitrary starting probability distribution. One step in the Markov chain involves the following:
- Move from $\alpha$ to a random element $g\in G$ that fixes $\alpha$.
- Move from $g$ to a random element $\beta\in \Omega$ that is fixed by $g$.
Since it is possible to move from any $\alpha$ to any $\beta$ in $\Omega$ in a single step (through the identity of $G$) the Markov chain is irreducible and aperiodic. This implies that there is a unique distribution that is approached by iterating the procedure above from any starting distribution. It's not hard to show that the limiting distribution is the one where all orbits are equally likely (i.e. the probability of reaching $\alpha$ is inversely proportional to the size of the orbit containing it).
I read about this nice construction in P.J. Cameron's "Permutation Groups", where he brings up what he calls a slogan of modern enumeration theory: "…the ability to count a set is closely related to the ability to pick a random element from that set (with all elements equally likely)."
One special case of this Markov chain is when we let $\Omega=G$ and the action be conjugation, then we get a limiting distribution where all conjugacy classes of $G$ are equally likely. Now, except for this nice result, it would also be interesting to know something about the rate of convergence of this chain. Cameron mentions that it is rapidly mixing (converges exponentially fast to the limiting distribution) in some important cases, but examples where it's not rapidly mixing can also be constructed. My question is:
Question: Can we describe the rate of convergence of the Markov chain described above in terms of group-theoretic concepts (properties of $G$)?
While giving the rate of convergence in terms of the properties of $G$ might be a hard question, answers with sufficient conditions for the chain to be rapidly mixing are also welcome.
Best Answer
This is a classical question which is now well understood, I believe. Start with this famous paper: http://tinyurl.com/yfyrg63 Although this question is really not about standard r.w. on groups, a survey by Saloff-Coste gives an excellent introduction and literature review: www.math.cornell.edu/~lsc/rwfg.pdf