This paper examines random walks on a finite group G and finds
upper bounds on how long it takes typical random walks supported on
$(\log|G|)^a$ elements to get close to uniformly distributed on G. For
certain groups, a cutoff phenomenon is shown to exist for these typical random
walks. A variation of the upper bound lemma of Diaconis and Shahshahani and
some counting arguments related to a group equation are used to get the upper
bound. A further example which uses this variation is discussed.
Publié le : 1996-04-14
Classification:
Random walk,
finite groups,
enumeration,
upper bound lemma,
60B15,
60J15,
05A18
@article{1039639374,
author = {Dou, Carl and Hildebrand, Martin},
title = {Enumeration and random random walks on finite groups},
journal = {Ann. Probab.},
volume = {24},
number = {2},
year = {1996},
pages = { 987-1000},
language = {en},
url = {http://dml.mathdoc.fr/item/1039639374}
}
Dou, Carl; Hildebrand, Martin. Enumeration and random random walks on finite groups. Ann. Probab., Tome 24 (1996) no. 2, pp. 987-1000. http://gdmltest.u-ga.fr/item/1039639374/