Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 8 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
I couldn't find anything related to this question there... –  Gjergji Zaimi Feb 14 '10 at 22:10
    
Damn, I'm sorry :( –  Tom LaGatta Feb 15 '10 at 1:44
add comment

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.

share|improve this answer
    
Thank you for the suggestion. Did you have any specific section in mind? I can't seem to find anything particularly relevant to this question. –  Gjergji Zaimi Feb 15 '10 at 0:50
    
Thinking about it some more, this setup is quite different from what's usually called "random walks on groups" and related things. So I wouldn't be surprised if no answer to your question is known. But the techniques needed to answer it are likely in the Peres-Levin-Wilmer book or chapters 7-8 of the Aldous-Fill book. –  Mark Meckes Feb 15 '10 at 12:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.