Cut-off for lamplighter chains on tori: dimension interpolation and phase transition
Authors
Dembo, Amir
Ding, Jian
Miller, JP
Peres, Yuval
Publication Date
2019-02-04Journal Title
Probability Theory and Related Fields
ISSN
1432-2064
Publisher
Springer Nature
Volume
173
Pages
605-650
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Dembo, A., Ding, J., Miller, J., & Peres, Y. (2019). Cut-off for lamplighter chains on tori: dimension interpolation and phase transition. Probability Theory and Related Fields, 173 605-650. https://doi.org/10.1007/s00440-018-0883-4
Abstract
Given a finite, connected graph $\SG$, the lamplighter chain
on $\SG$ is the lazy random walk $X^\diamond$ on the associated
lamplighter graph $\SG^\diamond=\Z_2 \wr \SG$.
The mixing time of the lamplighter chain on the torus $\Z_n^d$ is known to have a cutoff at a time asymptotic to the cover time of $\Z_n^d$ if $d=2$, and to half the cover time if $d \ge 3$. We show that the mixing time of the lamplighter chain on $\ttorus=\Z_n^2 \times \Z_{a \log n}$ has a cutoff at $\psi(a)$ times the cover time of $\ttorus$ as $n \to \infty$, where $\psi$ is an explicit weakly decreasing map from $(0,\infty)$ onto $[1/2,1)$. In particular, as $a > 0$ varies, the threshold continuously interpolates between the known thresholds for $\Z_n^2$ and $\Z_n^3$. Perhaps surprisingly, we find a phase transition
(non-smoothness of $\psi$) at the point $a_*=\pi r_3 (1+\sqrt{2})$,
where high dimensional behavior ($\psi(a)=1/2$ for all $a \ge a_*$)
commences. Here $r_3$ is the effective resistance from $0$ to $\infty$ in $\Z^3$.
Keywords
Wreath product, Lamplighter walk, Mixing time, Cutoff, Uncovered set
Embargo Lift Date
2100-01-01
Identifiers
External DOI: https://doi.org/10.1007/s00440-018-0883-4
This record's URL: https://www.repository.cam.ac.uk/handle/1810/288059
Rights
All rights reserved
Licence:
http://www.rioxx.net/licenses/all-rights-reserved
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk