Mixing and relaxation time for random walk on wreath product graphs. (English) Zbl 1408.60060

Summary: 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^\diamond\) 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^\diamond\) 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\neq x,y\) remains unchanged. We estimate the mixing time of \(X^\diamond\) in terms of the parameters of \(H\) and \(G\). Further, we show that the relaxation time of \(X^\diamond\) is the same order as the maximal expected hitting time of \(G\) plus \(|G|\) times the relaxation time of the chain on \(H\).


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