Walks on generating sets of groups
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.
scientific article; zbMATH DE number 1230009