Markov chain on Groups - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T16:33:32Z http://mathoverflow.net/feeds/question/15219 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/15219/markov-chain-on-groups Markov chain on Groups Gjergji Zaimi 2010-02-14T00:39:58Z 2010-02-16T19:21:13Z <p>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:</p> <ul> <li>Move from $\alpha$ to a random element $g\in G$ that fixes $\alpha$. <li>Move from $g$ to a random element $\beta\in \Omega$ that is fixed by $g$. </ul> <p>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).</p> <p><hr /></p> <p>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)." </p> <p>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:</p> <blockquote> <p>Question: Can we describe the rate of convergence of the Markov chain described above in terms of group-theoretic concepts (properties of $G$)?</p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/15219/markov-chain-on-groups/15234#15234 Answer by Tom LaGatta for Markov chain on Groups Tom LaGatta 2010-02-14T05:02:38Z 2010-02-14T05:02:38Z <p>I'm not sure, but I'll bet you can find the answer in the recent book <a href="http://www.ams.org/bookpages/mbk-58/" rel="nofollow">Markov Chains and Mixing Times</a> by Peres, Levin and Wilmer.</p> http://mathoverflow.net/questions/15219/markov-chain-on-groups/15263#15263 Answer by Mark Meckes for Markov chain on Groups Mark Meckes 2010-02-14T15:55:51Z 2010-02-14T19:30:36Z <p>I second Tom's suggestion. Another place to look is the not-yet-published book <a href="http://www.stat.berkeley.edu/~aldous/RWG/book.html" rel="nofollow">Reversible Markov Chains and Random Walks on Graphs</a> by Aldous and Fill.</p> http://mathoverflow.net/questions/15219/markov-chain-on-groups/15483#15483 Answer by Igor Pak for Markov chain on Groups Igor Pak 2010-02-16T19:21:13Z 2010-02-16T19:21:13Z <p>This is a classical question which is now well understood, I believe. Start with this famous paper: <a href="http://tinyurl.com/yfyrg63" rel="nofollow">http://tinyurl.com/yfyrg63</a> 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 </p>