A curiously slowly mixing Markov chain
Persi Diaconis Department of Mathematics Stanford University Andrew Lin Department of Mathematics Stanford University Arun Ram Department of Mathematics University of Melbourne · 2025
Read A curiously slowly mixing Markov chain by Persi Diaconis Department of Mathematics Stanford University Andrew Lin Department of Mathematics Stanford University Arun Ram Department of Mathematics University of Melbourne (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01245.txt.
Introduction
Persi Diaconis, Andrew Lin, and Arun Ram exhibit a Markov chain whose speed of mixing depends curiously on how mixing is measured. The chain is the Burnside process on the hypercube, a sampling scheme built from group actions, here on binary strings of length n.
Started from the all zeros state, the chain mixes in a bounded number of steps, however large n grows, in both the l1 and l2 senses. From a general starting point it still mixes within about log n steps in l1. But in l2, most starting points need on the order of n divided by log n steps, vastly slower. The l2 results come from diagonalizing the chain explicitly, with eigenvectors valued in binomial coefficients.
Catalog record
| CREATOR | Persi Diaconis Department of Mathematics Stanford University Andrew Lin Department of Mathematics Stanford University Arun Ram Department of Mathematics University of Melbourne |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 218 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-01245