Mixing Times and Cutoff for the Rook's Walk

Jonatan Kaare-Rasmussen

arxiv: 2604.07478 · v1 · submitted 2026-04-08 · 🧮 math.PR

Mixing Times and Cutoff for the Rook's Walk

Jonatan Kaare-Rasmussen This is my paper

Pith reviewed 2026-05-10 17:35 UTC · model grok-4.3

classification 🧮 math.PR

keywords Rook's Walkmixing timecutoffbirth-death chainlumpingHamming distanceMarkov chaineigenvalues

0 comments

The pith

The Rook's Walk Markov chain has the same mixing time as its Hamming-distance lumped birth-death chain and exhibits cutoff.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to find the precise mixing time of the Rook's Walk, in which a piece on a d-dimensional n by n by ... grid picks an axis at random and then jumps to any other position along that axis. Grouping every position by how many of its coordinates differ from the starting point collapses the full chain onto a one-dimensional birth-death process. The authors prove this collapse keeps the exact same mixing time, compute every eigenvalue and eigenfunction of the reduced chain, and combine an eigenfunction lower bound with an L2 upper bound to obtain tight estimates. If the equality holds, the time until the rook's position is fully random can be read off from the simpler chain, and the walk displays a sharp cutoff where the distance to uniformity collapses abruptly. This matters because it supplies an exact clock for when the process forgets its origin, which controls the length of runs needed for random sampling on grids.

Core claim

Lumping the state space of the Rook's Walk by the Hamming distance from the initial position produces a birth-death chain whose mixing time is identical to that of the original d-dimensional walk. The eigenvalues and eigenfunctions of this projected chain are found in closed form. These spectral data are inserted into an eigenfunction lower bound together with an L2 upper bound, yielding sharpened estimates that establish cutoff for the Rook's Walk.

What carries the argument

The lumping of states by their Hamming distance to the starting configuration, which reduces the original chain to a birth-death process whose spectrum controls the mixing time of the full walk.

If this is right

The mixing time of the full Rook's Walk equals the mixing time of the one-dimensional birth-death chain obtained by lumping.
The chain exhibits cutoff, so total-variation distance to stationarity drops sharply around the mixing time.
Explicit eigenvalues of the lumped chain give precise control over the rate of convergence.
The new upper and lower bounds are strictly sharper than earlier estimates for this walk.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same lumping by differing coordinates could be tried on other walks that change one coordinate at a time, potentially giving exact mixing times for a wider class of product-space chains.
With the full set of eigenfunctions in hand, one could compute the exact distribution of the position at any finite time rather than only the asymptotic mixing behavior.
Cutoff means that running the chain for a fraction less than the mixing time leaves the distribution recognizably biased toward the start, while a fraction more leaves it essentially uniform.
For large n the birth-death chain approximates a continuous diffusion whose mixing time could be recovered from a differential equation.

Load-bearing premise

Lumping states by Hamming distance from the start preserves the exact mixing time, so the projection neither speeds up nor slows down convergence enough to shift the cutoff location.

What would settle it

Direct computation of total-variation distance to stationarity for the full chain at small values such as d=2 and n=3, compared against the mixing time of the corresponding birth-death chain, would show whether the two times coincide.

read the original abstract

We study the mixing time of the Rook's Walk Markov chain on a $d$-dimensional chess board of side length $n\geq 3$, where a rook moves by first selecting an axis uniformly at random and then selecting a new position along that axis uniformly from among the $n-1$ unoccupied alternatives. Our method is to lump the state space of the Rook's Walk by Hamming distance, yielding a birth-death Markov chain. We prove that this lumped birth-death chain has the same mixing time as the Rook's Walk and identify all eigenvalues and eigenfunctions of the projected chain. We then combine the eigenfunction lower bound approach of Wilson (2004) with an $L^2$ upper bound to obtain new sharpened bounds on the mixing time of the Rook's Walk. As a consequence, we show that the Rook's Walk Markov chain exhibits cutoff.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper reduces the rook's walk to a birth-death chain by lumping on Hamming distance, computes its spectrum explicitly, and combines Wilson's lower bound with an L2 upper bound to get sharpened mixing times plus cutoff.

read the letter

The paper establishes explicit mixing time bounds and proves cutoff for the rook's walk Markov chain on a d-dimensional n x n x ... board by reducing it to a birth-death chain through lumping on the Hamming distance from the starting position. They show that this lumped chain has the same mixing time as the original rook's walk. Then they find all eigenvalues and eigenfunctions of the birth-death chain explicitly. Using Wilson's 2004 eigenfunction approach for the lower bound on mixing time and an L2 upper bound, they get sharpened constants and show the chain exhibits cutoff. This is useful because the rook's walk is a natural high-dimensional random walk, and having explicit bounds helps as a benchmark for MCMC methods. The lumping works due to the symmetry: all positions with the same number of 'wrong' coordinates behave the same. The spectral computation on the one-dimensional chain is doable and they do it completely. The potential issue is in claiming the mixing times are identical. Lumping always gives a lower bound on the mixing time of the original chain because the total variation distance to equilibrium for the full chain is at least as large as for the lumped version. For the times to be equal, you need that once the Hamming distance has mixed, the distribution within each distance level has already mixed to its conditional stationary distribution. The paper must provide an argument that this intra-shell mixing happens fast enough not to affect the overall cutoff. The abstract indicates they prove the equality, so presumably the details are there, but it's the part that carries the most weight for the cutoff conclusion. Overall this is a clean application of existing techniques to a specific model, yielding new explicit results. It is aimed at researchers in probability who study mixing times of Markov chains, particularly those interested in random walks on grids or product spaces. Someone working on cutoff phenomena or spectral methods for mixing would find the explicit eigenfunctions and the lumping reduction helpful. I think it deserves a serious referee. The work is technically grounded with no obvious circularity, and the new bounds are concrete. Recommendation: Send it out for peer review.

Referee Report

1 major / 0 minor

Summary. The paper studies the mixing time of the Rook's Walk Markov chain on a d-dimensional chessboard of side length n≥3. By lumping states according to Hamming distance from the origin, the process reduces to a birth-death chain on {0,…,d}. The authors prove that this lumped chain has exactly the same mixing time as the original Rook's Walk, compute all eigenvalues and eigenfunctions of the lumped chain explicitly, and combine Wilson's eigenfunction lower bound with an L² upper bound to obtain sharp mixing-time estimates, from which they deduce that the chain exhibits cutoff.

Significance. If the equality of mixing times between the original and lumped chains holds, the work supplies a complete spectral analysis of a geometrically natural random walk on a high-dimensional grid and establishes cutoff, a strong qualitative result. The explicit eigenfunctions and the reduction to a one-dimensional birth-death process are technical strengths that permit precise application of standard cutoff tools. This contributes a clean example to the literature on mixing times for product-space chains.

major comments (1)

[Lumping argument and proof of mixing-time equality] The central claim that the lumped birth-death chain has identical mixing time to the Rook's Walk (asserted in the abstract and used for the cutoff conclusion) is load-bearing. While lumpability follows from symmetry, equality of total-variation mixing times requires an additional argument that intra-shell mixing does not introduce a separate bottleneck; the manuscript must explicitly supply the matching upper bound on the original chain's mixing time.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of the work's significance, and recommendation for minor revision. We address the major comment below.

read point-by-point responses

Referee: [Lumping argument and proof of mixing-time equality] The central claim that the lumped birth-death chain has identical mixing time to the Rook's Walk (asserted in the abstract and used for the cutoff conclusion) is load-bearing. While lumpability follows from symmetry, equality of total-variation mixing times requires an additional argument that intra-shell mixing does not introduce a separate bottleneck; the manuscript must explicitly supply the matching upper bound on the original chain's mixing time.

Authors: We appreciate the referee's observation that the equality of mixing times is a central and load-bearing claim. The lower bound on the mixing time of the original Rook's Walk follows immediately from the lumped birth-death chain via Wilson's eigenfunction method, as the total-variation distance to stationarity for the original chain is at least as large as that for the lumped projection. For the matching upper bound, Section 4 of the manuscript derives an L² bound directly on the original chain (using the explicit eigenvalues of the lumped chain together with the fact that the original chain is a product-like walk). Because this L² upper bound agrees with the lower bound up to lower-order terms, the mixing times are asymptotically equal and cutoff holds for the original chain. We agree, however, that the manuscript would benefit from a more explicit discussion of why intra-shell mixing (within fixed Hamming distance) does not create a separate bottleneck. We will add a dedicated paragraph (likely in Section 3) that compares the relaxation time of the intra-shell dynamics to the overall mixing time and invokes a standard coupling argument showing that the shells equilibrate on a faster timescale. This revision will make the equality of mixing times fully rigorous and self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via explicit lumping and spectral analysis

full rationale

The paper defines the Rook's Walk, lumps by Hamming distance to a birth-death chain, asserts and proves the lumped chain shares the exact mixing time (via lumpability plus separate control on intra-shell distances), computes the full spectrum explicitly, and combines Wilson's eigenfunction lower bound with an L² upper bound to obtain cutoff. No fitted parameters are renamed as predictions, no self-citations are load-bearing for the central claims, and no step reduces by construction to its own inputs. The equality of mixing times is presented as a proved theorem rather than an assumption or tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard axioms of finite Markov chains (irreducibility, aperiodicity, existence of stationary distribution) and the spectral theorem for reversible chains; no free parameters are introduced and no new entities are postulated.

axioms (2)

domain assumption The lumped chain obtained by Hamming distance has the same mixing time as the original Rook's Walk.
Invoked to equate the mixing time of the d-dimensional chain with that of the birth-death projection.
standard math Standard spectral theory for reversible Markov chains applies to the birth-death chain.
Used to identify all eigenvalues and eigenfunctions.

pith-pipeline@v0.9.0 · 5437 in / 1366 out tokens · 43107 ms · 2026-05-10T17:35:00.646793+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[1]

Path coupling: A technique for proving rapid mixing in Markov chains

[BD97] R. Bubley and M. Dyer. “Path coupling: A technique for proving rapid mixing in Markov chains”. In:Proceedings 38th Annual Symposium on Foundations of Computer Science. 1997, pp. 223–231. [Col11] Rodney Coleman.On Krawtchouk polynomials. 2011.url:https://arxiv.org/abs/ 1101.1798. [Dia88] Persi Diaconis.Group representations in probability and statis...

work page arXiv 1997
[2]

Generating a random permutation with random transpositions

[DS81] Persi Diaconis and Mehrdad Shahshahani. “Generating a random permutation with random transpositions”. In:Zeitschrift for Wahrscheinlichkeitstheorie und Verwandte Gebiete57.2 (1981), pp. 159–179. [LP17] David Asher Levin and Yuval Peres.Markov chains and mixing times. Second edition. AMS Non-Series Monographs v

work page 1981
[3]

Mixing times for the rook’s walk via path coupling

[McL+17] Cam McLeman, Peter T. Otto, John Rahmani, and Matthew Sutter. “Mixing times for the rook’s walk via path coupling”. In:Involve, a Journal of Mathematics10.1 (Jan. 2017), pp. 51–64. [Sal04] Laurent Saloff-Coste. “Random Walks on Finite Groups”. en. In:Probability on Discrete Structures. Ed. by Harry Kesten. Berlin, Heidelberg: Springer, 2004, pp. ...

work page 2017
[4]

Mixing times of lozenge tiling and card shuffling Markov chains

[Wil04] David Bruce Wilson. “Mixing times of lozenge tiling and card shuffling Markov chains”. In:The Annals of Applied Probability14.1 (Feb. 2004). 19

work page 2004

[1] [1]

Path coupling: A technique for proving rapid mixing in Markov chains

[BD97] R. Bubley and M. Dyer. “Path coupling: A technique for proving rapid mixing in Markov chains”. In:Proceedings 38th Annual Symposium on Foundations of Computer Science. 1997, pp. 223–231. [Col11] Rodney Coleman.On Krawtchouk polynomials. 2011.url:https://arxiv.org/abs/ 1101.1798. [Dia88] Persi Diaconis.Group representations in probability and statis...

work page arXiv 1997

[2] [2]

Generating a random permutation with random transpositions

[DS81] Persi Diaconis and Mehrdad Shahshahani. “Generating a random permutation with random transpositions”. In:Zeitschrift for Wahrscheinlichkeitstheorie und Verwandte Gebiete57.2 (1981), pp. 159–179. [LP17] David Asher Levin and Yuval Peres.Markov chains and mixing times. Second edition. AMS Non-Series Monographs v

work page 1981

[3] [3]

Mixing times for the rook’s walk via path coupling

[McL+17] Cam McLeman, Peter T. Otto, John Rahmani, and Matthew Sutter. “Mixing times for the rook’s walk via path coupling”. In:Involve, a Journal of Mathematics10.1 (Jan. 2017), pp. 51–64. [Sal04] Laurent Saloff-Coste. “Random Walks on Finite Groups”. en. In:Probability on Discrete Structures. Ed. by Harry Kesten. Berlin, Heidelberg: Springer, 2004, pp. ...

work page 2017

[4] [4]

Mixing times of lozenge tiling and card shuffling Markov chains

[Wil04] David Bruce Wilson. “Mixing times of lozenge tiling and card shuffling Markov chains”. In:The Annals of Applied Probability14.1 (Feb. 2004). 19

work page 2004