Random Lazy Random Walks on Arbitrary Finite Groups

This paper considers lazy random walks supported on a random subset of k elements of a finite group G with order n. If k=a log₂n where a>1 is constant, then most such walks take no more than a multiple of log₂n steps to get close to uniformly distributed on G. If k=log₂n+f(n) where f(n) and f(n)/log₂n0 as n, then most such walks take no more than a multiple of (log₂n) ln(log₂n) steps to get close to uniformly distributed. To get these results, this paper extends techniques of Erdös and Rényi and of Pak.