Uniform mixing time for random walk on lamplighter graphs

DOI10.1214/13-AIHP547MaRDI QIDQ479701zbMATH OpenOpenAlexFDO

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

Publication date 5 December 2014

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

Full work available at URL https://arxiv.org/abs/1109.4281, https://projecteuclid.org/euclid.aihp/1413555494

zbMATH Keywords

lamplighter graphsmixing timerandom walks

Mathematics Subject Classification ID

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

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.

Review text

The authors find a concentration estimate for the local time of a peculiar random walk in a subset of vertices in order to study the uniform mixing time for random walks on lamplighter graphs. A previous study was carried out by the third author and \textit{D. Revelle} in [Electron. J. Probab. 9, Paper No. 26, 825--845 (2004; Zbl 1064.60095)].

Recommendations

• Mixing times for random walks on finite lamplighter groups
• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
• Mixing and relaxation time for random walk on wreath product graphs
• Cutoff for lamplighter chains on fractals
• On sensitivity of uniform mixing times

Cites work

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

Cited in

(6)

• On sensitivity of uniform mixing times
• Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
• Mixing times for random walks on finite lamplighter groups
• Mixing and relaxation time for random walk on wreath product graphs
• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains
• Upgrading MLSI to LSI for reversible Markov chains

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)