Walks on generating sets of groups
type: Item
instance of: scholarly article
title: Walks on generating sets of groups
zbMATH Open document ID: 0921.60003
author: Persi Diaconis
author: Laurent Saloff-Coste
published in: Inventiones Mathematicae
publication date: 1998-12-06T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 60B10
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 20F05
zbMATH DE Number: 1230009
zbMATH Keywords: Celler algorithm
zbMATH Keywords: Markov chain
zbMATH Keywords: generator of a group
zbMATH Keywords: convergence to equilibrium
zbMATH Keywords: rate of convergence
reviewed by: Arnold Janssen
MaRDI profile type: Publication
full work available at URL: s002220050265
OpenAlex ID: W1991127083
DOI: 10.1007/S002220050265
description: scientific article; zbMATH DE number 1230009