How to cite item

Random Walks On Finite Groups With Few Random Generators

   
@article{EJP38,
	author = {Igor Pak},
	title = {Random Walks On Finite Groups With Few Random Generators},
	journal = {Electron. J. Probab.},
	fjournal = {Electronic Journal of Probability},
	volume = {4},
	year = {1998},
	keywords = {Random random walks on groups, random subproducts, probabilistic method, separation distance},
	abstract = {Let $G$ be a finite group. Choose a set $S$ of size $k$ uniformly from $G$ and consider a lazy random walk on the corresponding Cayley graph. We show that for almost all choices of $S$ given $k = 2a\, \log_2 |G|$, $a>1$, this walk mixes in under $m = 2a \,\log\frac{a}{a-1} \log |G|$ steps. A similar result was obtained earlier by Alon and Roichman and also by Dou and Hildebrand  using a different techniques. We also prove that when sets are of size $k = \log_2 |G| + O(\log \log |G|)$, $m = O(\log^3 |G|)$ steps suffice for mixing of the corresponding symmetric lazy random walk. Finally, when $G$ is abelian we obtain better bounds in both cases.},
	pages = {no. 1, 1-11},
	issn = {1083-6489},
	doi = {10.1214/EJP.v4-38},    
        url = {http://ejp.ejpecp.org/article/view/38}}