Random walks on finite groups with few random generators. (English) Zbl 0918.60061

Pak, Igor

Electron. J. Probab. 4, Paper No. 1, 11 p. (1999).

Summary: 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 {a\over a-1} \log| G|\) steps. A similar result was obtained earlier by N. Alon and Y. Roichman [Random Struct. Algorithms 5, No. 2, 271-284 (1994; Zbl 0798.05048)] and C. Dou and M. Hildebrand [Ann. Probab. 24, No. 2, 987-1000 (1996; Zbl 0862.60006)] using a different technique. 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.

MSC:

60G50	Sums of independent random variables; random walks
60C05	Combinatorial probability

Keywords:

random walks on groups; random subproducts; probabilistic method; separation distance

Citations:

Zbl 0798.05048; Zbl 0862.60006