Mixing of the Aldous-Fill crossover chain via random switching networks
Aldous and Fill consider a chain on K binary words of length L: at each step the words are paired at random, and within each pair every letter position is exchanged with probability 1/2. They prove that it mixes in $O(K\log L)$ steps and ask for $O(\log K\cdot\log L)$. We show that it mixes in $O(\log K+\log L)$ steps. Given the pairings, the letter positions evolve independently, each pushed through the same random switching network, and Czumaj proved that almost every such network of logarithmic depth shuffles every 0–1 vector almost uniformly. We also prove the lower bounds $\log_2\min(K,L)-3$ and, for fixed K ≥ 4, a constant times $\log L$.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-15
- DOI
- https://doi.org/10.5281/zenodo.24257129
- Primary Topic
- Markov Chains and Monte Carlo Methods
- Type
- preprint