Uniform mixing time for random walk on lamplighter graphs

DOI10.1214/13-AIHP547zbMATH Open1318.60053arXiv1109.4281OpenAlexW3105367601MaRDI QIDQ479701FDOQ479701

Jason Miller, Yuval Peres, Júlia Komjáthy

Publication date: 5 December 2014

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Abstract: Suppose that $CG$ is a finite, connected graph and $X$ is a lazy random walk on $CG$. The lamplighter chain $X^{d}iamond$ associated with $X$ is the random walk on the wreath product $$, the graph whose vertices consist of pairs $(f,x)$ where $f$ is a labeling of the vertices of $CG$ by elements of $$ and $x$ is a vertex in $CG$. There is an edge between $(f,x)$ and $(g,y)$ in $C{G}^{d}iamond$ if and only if $x$ is adjacent to $y$ in $CG$ and $f(z)=g(z)$ for all $zeqx,y$. In each step, $X^{d}iamond$ moves from a configuration $(f,x)$ by updating $x$ to $y$ using the transition rule of $X$ and then sampling both $f(x)$ and $f(y)$ according to the uniform distribution on $$; $f(z)$ for $zeqx,y$ remains unchanged. We give matching upper and lower bounds on the uniform mixing time of $X^{d}iamond$ provided $CG$ satisfies mild hypotheses. In particular, when $CG$ is the hypercube $$, we show that the uniform mixing time of $X^{d}iamond$ is $Theta(d{2}^d)$. More generally, we show that when $CG$ is a torus $$ for $dgeq3$, the uniform mixing time of $X^{d}iamond$ is $Theta(d{n}^d)$ uniformly in $n$ and $d$. A critical ingredient for our proof is a concentration estimate for the local time of random walk in a subset of vertices.

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

zbMATH Keywords

random walksmixing timelamplighter graphs

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Ergodicity, mixing, rates of mixing (37A25) Random walks on graphs (05C81) Local time and additive functionals (60J55)

Cites Work

• Random Walk: A Modern Introduction
• Cover times for Brownian motion and random walks in two dimensions
• Late points for random walks in two dimensions
• Comparison techniques for random walk on finite groups
• Logarithmic Sobolev inequalities for finite Markov chains
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Rates of convergence for lamplighter processes
• Mixing times for random walks on finite lamplighter groups
• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains

Cited In (4)

• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
• Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
• Upgrading MLSI to LSI for reversible Markov chains
• Mixing times for random walks on finite lamplighter groups

This page was built for publication: Uniform mixing time for random walk on lamplighter graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q479701)