Walks on generating sets of groups (Q1273297): Difference between revisions

The new Celler et al. algorithm for generating random elements of a finite group \(G\) by a generator \(S\) is studied in detail. This method is compared with older random walks which multiply at random elements of \(S\) in order to get a path in \(G\). The new Markov chain has faster convergence to equilibrium. The present paper provides the first quantitative bounds for the convergence of the Celler Markov chain. It contains a lot of concrete examples, for instance of walks on generating sets. A motivation are applications in computational group theory. It is interesting to see how everything works and that strong results for the groups are obtained by the new Markov chain.