Random lazy random walks on arbitrary finite groups (Q5950026)

A ``random random walk'' on a finite group \(G\) is defined by choosing a random subset \(S\) of \(G\) (often of some specified size \(k\)) and then performing a random walk on \(G\) where one starts at the identity and at each step one multiplies the previous position by a random element of \(S\). A ``random lazy random walk'' is obtained when at each step one multiplies by the identity with probability one-half and otherwise by a random element of \(S\). \textit{I. Pak} [Electron. J. Probab. 4, No. 1 (1999; Zbl 0918.60061)] obtained work on these lazy random walks, using earlier results of Erdős and Rényi. In the paper under review, the author extends the techniques of Erdős and Rényi and of Pak. He considers lazy random walks supported on a random subset of size \(k\) in a finite group \(G\) of order \(n\) to prove the following. If \(k=[a\log_2 n]\) where \(a>1\) is a constant, then most such walks take no more than a multiple of \(\log_2 n\) steps to get close to uniformly distributed on \(G\). If \(k=\log_2 n + f(n)\) where \(n\to\infty\) and \(f(n)/\log_2 n\to 0\) as \(n\to\infty\), then most of such walks take no more than a multiple of \((\log_2 n)\ln(\log_2 n)\) steps to get close to uniformly distributed. The paper ends with a few open problems.