|
Abstract : |
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 = 2 a log 2 jGj, a? 1, this walk mixes in under m = 2 a log a a\Gamma1 log jGj steps. A similar result was obtained earlier by Alon and Roichman (see [AR]), Dou and Hildebrand (see [DH]) using a different techniques. We also prove that when sets are of size k = log 2 jGj+O(log log jGj), m = O(log 3 jGj) steps suffice for mixing of the corresponding symmetric lazy random walk. Finally, when G is abelian we obtain better bounds in both cases., |
