Markov chain on Groups

2010-02-14T00:39:58Z

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.

Answer by Tom LaGatta for Markov chain on Groups

2010-02-14T05:02:38Z

I'm not sure, but I'll bet you can find the answer in the recent book Markov Chains and Mixing Times by Peres, Levin and Wilmer.

Answer by Mark Meckes for Markov chain on Groups

2010-02-14T15:55:51Z

I second Tom's suggestion. Another place to look is the not-yet-published book Reversible Markov Chains and Random Walks on Graphs by Aldous and Fill.

Answer by Igor Pak for Markov chain on Groups

2010-02-16T19:21:13Z

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

Markov chain on Groups - MathOverflow

Markov chain on Groups

Answer by Tom LaGatta for Markov chain on Groups

Answer by Mark Meckes for Markov chain on Groups

Answer by Igor Pak for Markov chain on Groups