Mixing and relaxation time for random walk on wreath product graphs

DOI10.1214/EJP.V18-2321zbMATH Open1408.60060arXiv1208.5930OpenAlexW2055134178MaRDI QIDQ388955FDOQ388955

Authors: Júlia Komjáthy, Yuval Peres 

Publication date: 17 January 2014

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

Abstract: Suppose that G and H are finite, connected graphs, G regular, X is a lazy random walk on G and Z is a reversible ergodic Markov chain on H. The generalized lamplighter chain X* associated with X and Z is the random walk on the wreath product Hwr G, the graph whose vertices consist of pairs (f,x) where f=(f_v)_{vin V(G)} is a labeling of the vertices of G by elements of H and x is a vertex in G. In each step, X* moves from a configuration (f,x) by updating x to y using the transition rule of X and then independently updating both f_x and f_y according to the transition probabilities on H; f_z for z different of x,y remains unchanged. We estimate the mixing time of X* in terms of the parameters of H and G. Further, we show that the relaxation time of X* is the same order as the maximal expected hitting time of G plus |G| times the relaxation time of the chain on H.

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

Recommendations

• Mixing times for random walks on finite lamplighter groups
• Uniform mixing time for random walk on lamplighter graphs
• Mixing times for Markov chains on wreath products and related homogeneous spaces
• Random walks on wreath products of groups
• Isoperimetry for wreath products of Markov chains and multiplicity of selfintersections of random walks

zbMATH Keywords

random walkmixing timerelaxation timewreath productgeneralized lamplighter walk

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Ergodicity, mixing, rates of mixing (37A25) Random walks on graphs (05C81) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Transition functions, generators and resolvents (60J35)

Cited In (5)

• Uniform mixing time for random walk on lamplighter graphs
• Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
• Assouad-Nagata dimension and gap for ordered metric spaces
• Topics in Markov chains: mixing and escape rate
• Mixing times for Markov chains on wreath products and related homogeneous spaces

This page was built for publication: Mixing and relaxation time for random walk on wreath product graphs

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