On random random walks
Roichman, Yuval
Ann. Probab., Tome 24 (1996) no. 2, p. 1001-1011 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We estimate the expected mixing time of a random walk on a finite group supported by a random polylogarithmic set of elements. Following the spectral approach of Broder and Shamir, we present an alternative proof of the Dou-Hildebrand estimate and show that it holds almost surely. Good bounds on diameters follow from these results.
Publié le : 1996-04-14
Classification:  Random walk,  finite groups,  diameters,  Cayley graphs,  60B15,  60J15,  05C25,  05C12 
@article{1039639375,
     author = {Roichman, Yuval},
     title = {On random random walks},
     journal = {Ann. Probab.},
     volume = {24},
     number = {2},
     year = {1996},
     pages = { 1001-1011},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1039639375}
}

Roichman, Yuval. On random random walks. Ann. Probab., Tome 24 (1996) no. 2, pp.  1001-1011. http://gdmltest.u-ga.fr/item/1039639375/