Random lazy random walks on arbitrary finite groups
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.
- Random walks on finite groups with few random generators
- Enumeration and random walks on finite groups
- A survey of results on random random walks on finite groups
- A Model for Random Random-Walks on Finite Groups
- First hitting times for some random walks on finite groups
- Random walks on generating sets for finite groups
- Random walks on finite groups with few random generators
- Random walks supported on random points of Z/nZ
- Random random walks on the integers mod \(n\)
- The complementary beta distribution
- A note on various holding probabilities for random lazy random walks on finite groups
- Enumeration and random walks on finite groups
- A Model for Random Random-Walks on Finite Groups
- scientific article; zbMATH DE number 3848354 (Why is no real title available?)
- Extension of a random walk on finite Abelian groups
- On binomial sums, additive energies, and lazy random walks
- Random walks on the lamplighter group
This page was built for publication: Random lazy random walks on arbitrary finite groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5950026)
