Hitting-time mixing for the star transposition shuffle
We prove a hitting-time analogue of cutoff for the star transposition shuffle on the symmetric group S_n. Let tau be the first time at which every non-top card has been selected. We show that the shuffle is asymptotically mixed at time tau: more precisely, the total variation distance between the law of Y_tau and the uniform distribution on S_n is at most exp(-(log n)^(1/2+o(1))). Our proof compares the star transposition shuffle with the random transposition shuffle using simultaneous diagonalization of the two transition kernels, and then adapts the hitting-time strategy of Jain and…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.13727
curl -X POST /api/v1/records/arxiv/2608.13727/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.13727/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'