Uniform mixing time for random walk on lamplighter graphs

J. Komjáthy, J. Miller, Y. Peres

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
77 Downloads (Pure)

Abstract

Suppose that G is a finite, connected graph and X is a lazy random walk on G . The lamplighter chain X ¿ associated with X is the random walk on the wreath product G ¿ =Z 2 ¿G , the graph whose vertices consist of pairs (f - ,x) where f is a labeling of the vertices of G by elements of Z 2 ={0,1} and x is a vertex in G . There is an edge between (f - ,x) and (g - ,y) in G ¿ if and only if x is adjacent to y in G and f z =g z for all z¿x,y . In each step, X ¿ 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 Z 2 ; f z for z¿x,y remains unchanged. We give matching upper and lower bounds on the uniform mixing time of X ¿ provided G satisfies mild hypotheses. In particular, when G is the hypercube Z d 2 , we show that the uniform mixing time of X ¿ is T(d2 d ) . More generally, we show that when G is a torus Z d n for d=3 , the uniform mixing time of X ¿ is T(dn d ) uniformly in n and d . A critical ingredient for our proof is a concentration estimate for the local time of the random walk in a subset of vertices.
Original languageEnglish
Pages (from-to)1140-1160
Number of pages21
JournalAnnales de l'institut Henri Poincare (B): Probability and Statistics
Volume50
Issue number4
DOIs
Publication statusPublished - 2014

Fingerprint Dive into the research topics of 'Uniform mixing time for random walk on lamplighter graphs'. Together they form a unique fingerprint.

Cite this