17
$\begingroup$

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.

$\endgroup$

4 Answers 4

9
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I couldn't find anything related to this question there... $\endgroup$ Feb 14, 2010 at 22:10
  • $\begingroup$ Damn, I'm sorry :( $\endgroup$ Feb 15, 2010 at 1:44
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Feb 15, 2010 at 0:50
  • $\begingroup$ 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. $\endgroup$ Feb 15, 2010 at 12:07
3
$\begingroup$

I recently published a paper on this exact problem for some classes of groups (link below). In short for CA groups I show that the rate of convergence is controlled the size of the group's center and the size of the largest centralizer of a non-central group element.

Link to paper or arXiv (also in Journal of theoretical probability): https://arxiv.org/abs/2003.04432

$\endgroup$
1
  • 1
    $\begingroup$ This is great! Thank you. $\endgroup$ Dec 3, 2020 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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