Mixing times for random walks on finite lamplighter groups

DOI10.1214/EJP.V9-198zbMATH Open1064.60095arXivmath/0404190MaRDI QIDQ1767530FDOQ1767530

Authors: Yuval Peres, David Revelle 

Publication date: 8 March 2005

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0404190

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

zbMATH Keywords

cover time

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15)

Cited In (20)

• Limits of random tree-like discrete structures
• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
• 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\)
• 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
• Some limits related to random iterations of a lamplighter group
• Upgrading MLSI to LSI for reversible Markov chains
• Assouad-Nagata dimension and gap for ordered metric spaces
• Words and mixing times in finite simple groups.
• First hitting times for some random walks on finite groups
• \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs
• Cutoff for lamplighter chains on fractals
• Nilprogressions and groups with moderate growth
• Speed of random walks, isoperimetry and compression of finitely generated groups
• Harmonic analysis of finite lamplighter random walks
• Topics in Markov chains: mixing and escape rate
• Diffusion limited aggregation on a cylinder
• Mixing and relaxation time for random walk on wreath product graphs
• Random walks on the lamplighter group

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)