Random Walks on Finite Groups

• Published in 2004
• Added on 2012-01-05

Markov chains on finite sets are used in a great variety of situations to approximate, understand and sample from their limit distribution. A familiar example is provided by card shuffling methods. From this viewpoint, one is interested in the “mixing time” of the chain, that is, the time at which the chain gives a good approximation of the limit distribution. A remarkable phenomenon known as the cut-off phenomenon asserts that this often happens abruptly so that it really makes sense to talk about “the mixing time”. Random walks on finite groups generalize card shuffling models by replacing the symmetric group by other finite groups. One then would like to understand how the structure of a particular class of groups relates to the mixing time of natural random walks on those groups. It turns out that this is an extremely rich problem which is very far to be understood. Techniques from a great variety of different fields – Probability, Algebra, Representation Theory, Functional Analysis, Geometry, Combinatorics – have been used to attack special instances of this problem. This article gives a general overview of this area of research.

Links

• http://statweb.stanford.edu/~cgates/PERSI/papers/rwfg.pdf

Other information

BibTeX entry

@article{Saloffcoste,
	key = {Saloffcoste},
	type = {article},
	title = {Random Walks on Finite Groups},
	author = {Saloff-coste, Laurent},
	abstract = {Markov chains on finite sets are used in a great variety of situations to approximate, understand and sample from their limit distribution. A familiar example is provided by card shuffling methods. From this viewpoint, one is interested in the “mixing time” of the chain, that is, the time at which the chain gives a good approximation of the limit distribution. A remarkable phenomenon known as the cut-off phenomenon asserts that this often happens abruptly so that it really makes sense to talk about “the mixing time”. Random walks on finite groups generalize card shuffling models by replacing the symmetric group by other finite groups. One then would like to understand how the structure of a particular class of groups relates to the mixing time of natural random walks on those groups. It turns out that this is an extremely rich problem which is very far to be understood. Techniques from a great variety of different fields – Probability, Algebra, Representation Theory, Functional Analysis, Geometry, Combinatorics – have been used to attack special instances of this problem. This article gives a general overview of this area of research.},
	comment = {},
	date_added = {2012-01-05},
	date_published = {2004-12-07},
	urls = {http://statweb.stanford.edu/{\~{}}cgates/PERSI/papers/rwfg.pdf},
	collections = {Probability and statistics,The groups group},
	url = {http://statweb.stanford.edu/{\~{}}cgates/PERSI/papers/rwfg.pdf},
	urldate = {2012-01-05},
	year = 2004
}