2012/08/31 by Júlia Komjáthy, Julia Komjathy, Yuval Peres
Chemistry · Computer Science · Mathematics · #Chemistry #Combinatorics #Diamond #Discrete mathematics #Ergodic theory #Geometry #Graph #Hitting time #Markov Chains and Monte Carlo Methods #Markov chain #Mathematical analysis #Mathematics #Mixing (physics) #Order (exchange) #Physics #Product (mathematics) #Quantum mechanics #Random walk #Relaxation (psychology) #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis #Vertex (graph theory) #Wreath product #math.PR
paper · pdf · doi:10.1214/ejp.v18-2321
published as Electronic Journal of Probability Volume 18 (2013), paper no. 71, 23 pp · 30 pages, 1 figure
arxiv created 2012/09/30 · openalex publication_date 2013/01/01 · arxiv updated 2016/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
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=(fv)v∈ V(G) is a labeling of the vertices of G by elements of H and x is a vertex in G. In each step, \diamond* moves from a configuration (f,x) by updating x to y using the transition rule of X and then independently updating both fx and fy according to the transition probabilities on H; fz for z different of 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.