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

CREATORPersi Diaconis Department of Mathematics Stanford University Andrew Lin Department of Mathematics Stanford University Arun Ram Department of Mathematics University of Melbourne
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE218 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01245

Browse the full library · About the Tower of Babel