Mixing Times and Cutoff for the Rook's Walk
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.07478
curl -X POST /api/v1/records/arxiv/2604.07478/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.07478/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'