@article{EJP2321,
author = {Júlia Komjáthy and Yuval Peres},
title = {Mixing and relaxation time for random walk on wreath product graphs},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {18},
year = {2013},
keywords = {Random Walk, Wreath Product Graphs, Mixing Time, Relaxation Time},
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 H\wr G, the graph whose vertices consist of pairs (f,x) where f=(f_v)_{v\in 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.},
pages = {no. 71, 1-23},
issn = {1083-6489},
doi = {10.1214/EJP.v18-2321},
url = {http://ejp.ejpecp.org/article/view/2321}}