Mixing times for random walks on finite lamplighter groups
From MaRDI portal
(Redirected from Publication:1767530)
Abstract: Given a finite graph G, a vertex of the lamplighter graph consists of a zero-one labeling of the vertices of G, and a marked vertex of G. For transitive graphs G, we show that, up to constants, the relaxation time for simple random walk in corresponding lamplighter graph is the maximal hitting time for simple random walk in G, while the mixing time in total variation on the lamplighter graph is the expected cover time on G. The mixing time in the uniform metric on the lamplighter graph admits a sharp threshold, and equals |G| multiplied by the relaxation time on G, up to a factor of log |G|. For the lamplighter group over the discrete two dimensional torus of sidelength n, the relaxation time is of order n^2 log n, the total variation mixing time is of order n^2 log^2 n, and the uniform mixing time is of order n^4. In dimension d>2, the relaxation time is of order n^d, the total variation mixing time is of order n^d log n, and the uniform mixing time is of order n^{d+2}. These are the first examples we know of of finite transitive graphs with uniformly bounded degrees where these three mixing time parameters are of different orders of magnitude.
Recommendations
- The mixing time for a random walk on the symmetric group generated by random involutions
- Random walks on the lamplighter group
- Weak mixing of random walks on groups
- Uniform mixing time for random walk on lamplighter graphs
- Rapidly mixing random walks and bounds on characters of the symmetric group
- First hitting times for some random walks on finite groups
- Mixing times for the commuting chain on CA groups
- scientific article; zbMATH DE number 2042290
Cited in
(22)- First hitting times for some random walks on finite groups
- Rates of convergence for lamplighter processes
- Cutoff for lamplighter chains on fractals
- Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
- Law of large numbers for the drift of the two-dimensional wreath product
- Limits of random tree-like discrete structures
- Speed of random walks, isoperimetry and compression of finitely generated groups
- Some limits related to random iterations of a lamplighter group
- Mixing and relaxation time for random walk on wreath product graphs
- Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
- Topics in Markov chains: mixing and escape rate
- Uniform mixing time for random walk on lamplighter graphs
- Uniformity of the late points of random walk on \({\mathbb {Z}}_{n}^{d}\) for \(d \geq 3\)
- \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs
- Assouad-Nagata dimension and gap for ordered metric spaces
- Upgrading MLSI to LSI for reversible Markov chains
- Harmonic analysis of finite lamplighter random walks
- Words and mixing times in finite simple groups.
- Random walks on the lamplighter group
- Expected hitting time estimates on finite graphs
- Nilprogressions and groups with moderate growth
- Diffusion limited aggregation on a cylinder
This page was built for publication: Mixing times for random walks on finite lamplighter groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1767530)
