Cutoff for q-deformed classical card shuffles in the type A Iwahori--Hecke algebra
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Cutoff for q-deformed classical card shuffles in the type A Iwahori--Hecke algebra".
Emmy: Here's the gist of the paper. We study three random walks of the type A Iwahori–Hecke algebra Hq(Sn) and prove that for fixed q > 1 they exhibit total variation and l2 cutoff at specific scales Chains and Operators The paper investigates three random walks on Hq(Sn): the short systematic scan, the q–random–to–random shuffle, and the q–deformed k–star transposition shuffle All three chains have the Mallows measure as their stationary distribution and can be viewed as combinations of Metropolis moves encoded by elements of Hq(Sn) The transition operators are quite different, but for fixed q > 1 they turn out to have the same mixing scales The short systematic scan is obtained by applying adjacent Metropolis moves successively in one direction and then in reverse The q–deformed k–star transposition shuffle is studied by diagonalizing it using Hecke Jucys–Murphy elements Spectral Analysis of the Shuffle The spectrum of the q–deformed k–star transposition shuffle P is analyzed, yielding eigenvalues indexed by standard Young tableaux S The eigenvalue of P indexed by S is given by eigq(S) = 1
n: q + q
n − 1: q
n: q Pk l=1
n − l: q X k l=1
cn+1−l(S): q The connection between these chains already appears before taking any limit, as the short systematic scan and P are affine functions of the same Jucys–Murphy element Jn(q) Mixing Times and Cutoffs For fixed q > 1, all three chains exhibit l2 cutoff at 1/2n + logq n with a constant-order window The total variation cutoff is at n squared with a window of at most order √n Specifically, the upper bound for the short systematic scan is improved both in the upper and lower bounds of Diaconis and Ram The total variation cutoff is at n squared with a window of at most order √n Limiting Dynamics and Lower Bounds As q → ∞, all three operators collapse to a single deterministic dynamics where the chain performs exactly those swaps which increase the number of inversions The limiting dynamics is deterministic, and its orbit starting from the identity gives the total variation lower bound for all of them The lower bound in total variation requires a different argument and is proved in Section 6 The three chains exhibit total variation cutoff at n squared with a window of at most order √n The scale √n appears only in this lower-bound argument The upper bound already gives mixing at n squared + 1/2 logq n + O(1) Conjecture 6.8 suggests the cutoff is at 1/2n + logq n with a window of order 1 The second limit has already been proved: it is Theorem 3.5 (respectively Corollary 3.9, Theorem 3.12) together with (5) and Theorem 1.3 Total Variation Cutoff The three chains exhibit total variation cutoff at n squared with a window of at most order √n The lower bound in total variation is derived from the identity, which is enough to bound tmix from below The three lower bounds above meet the upper bounds of Section 3 at the same time, which gives us the cutoff Final Result on Cutoff The q–deformed k–star transposition shuffle, the q–random–to–random shuffle, and the short systematic scan all exhibit l2 cutoff at 1/2n + logq n with a window of order 1 In particular, by Theorem 4.7, for n ≥ 4, K t id π - 1 TV ≥ q c - 1/2 The three chains exhibit total variation cutoff at n squared with a window of at most order √n The paper proves that for fixed q > 1, all three chains exhibit l2 cutoff at 1/2n + logq n with a constant-order window The total variation cutoff is at n squared with a window of at most order √n This result holds for the q–deformed k–star transposition shuffle, the q–random–to–random shuffle, and the short systematic scan The second limit has already been proved: it is Theorem 3.5 (respectively Corollary 3.9, Theorem 3.12) together with (5) and Theorem 1.3 The first is open only in the range n squared - O(√n) ≤ t ≤ n squared + 1/2 logq n Acknowledgements We are deeply grateful to Persi Diaconis for many generous and illuminating conversations, from which this work has benefited greatly We also thank our advisor, Evita Nestoridi, for her invaluable guidance throughout this project The first author thanks Colin Defant for useful discussions References
1: Samira Arfaee and Bryan Wong.
Ada: “Cutoff for q-deformed classical card shuffles in the type A Iwahori–Hecke algebra”
2: Ilani Axelrod-Freed et al.
Emmy: “Spectrum of random-to-random shuffling in the Hecke algebra”
3: Michael E.
Ada: Bate, Stephen B.
Paper summary: Ada: So we're looking at this paper now, "Cutoff for q-deformed classical card shuffles in the type A Iwahori--Hecke algebra". The main thing here is studying three different random walks on this Hecke algebra Hq(Sn).
Emmy: It’s about the short systematic scan, the q–deformed random–to–random shuffle, and this q–deformed k-star transposition shuffle. The authors use the spectra of these chains to look at how fast they mix.
Kolya: So what they are claiming is that for any fixed number q greater than one, all three of these different shuffling processes exhibit both an l two cutoff and a total variation cutoff at specific scales.
Ada: That’s the core thesis: for fixed q greater than one, these chains all show l two cutoff and total variation cutoff at specific scales. What makes this interesting is that they study three very different types of shuffles using the same underlying algebraic structure.
Emmy: Exactly. It suggests that even with these different moves, when you use this Hecke algebra setting, the mixing behavior settles down at comparable speeds for fixed q greater than one. It connects the structure of these random walks to their actual performance on mixing time.
Kolya: I wonder what this means for the practical application of shuffling algorithms? If they all have these cutoffs, does that give us a general idea of how hard it is to mix a deck using these kinds of moves?
Ada: That’s a good question. Kolya, if we look at the results, they find an l two cutoff at one over two n plus log q n with a constant order window for all three chains.
Emmy: And on top of that, they establish a total variation cutoff at n squared with a window of at most order root n. They even mention that for the short systematic scan, these bounds improve both the upper and lower bounds from Diaconis and Ram ten <ref:2609.13570#pg1,improve both the upper and lower bounds>.
Kolya: Wait, so we have two different scale cutoffs here. One is this one over two n plus log q n for l two cutoff, which seems pretty tight. And then there's the total variation cutoff at n squared with a window of at most root n. How do those relate to what we usually see in mixing time analysis?
Ada: Well, Kolya, the l two cutoff is about how quickly the probability distribution approaches its stationary state in terms of its second moment. The total variation cutoff tells us about the convergence in terms of total variation distance.
Emmy: And what’s striking is that for fixed q greater than one, they find these cutoffs are achieved with a constant order window for the l two cutoff, which is a nice structural property. This structure seems to be inherited from the spectrum analysis they did on the q–deformed k-star transposition shuffle.
Paper summary: Kolya: I see. So even though we have three different walks—the scan, the random-to-random shuffle, and the k-star transposition shuffle—they all share this characteristic convergence speed for fixed q greater than one. Does this imply something about how robust these types of shuffles are to the specific move chosen?
Ada: It implies a certain level of universality in the mixing behavior when viewed through this Hecke algebra lens. The paper shows that the algebraic connection between these chains, like them being affine functions of the same jucys–murphy element j n q, is key to proving this shared scaling.
Emmy: That’s right. The connection they make between the short systematic scan and the transposition shuffle is important because it means they aren't studying three completely independent things; there’s a structural link between them that forces their mixing scales to align for fixed q greater than one.
Kolya: So, if we look at the limit as q goes to infinity, what happens? The paper mentions that all three operators collapse to a single deterministic dynamics. What does that deterministic thing look like?
Ada: As q goes to infinity, the operators all simplify into one single deterministic process where the chain performs exactly those swaps which increase the number of inversions in a deck. This limiting dynamics is deterministic, and its orbit starting from the identity gives us a total variation lower bound for all of them.
Emmy: That deterministic limit provides a benchmark for understanding the lower bound on mixing time for these walks. It’s like knowing what the absolute slowest they can possibly mix in this setting.
Kolya: So, if we take that limiting dynamics result—the orbit of the identity giving a lower bound—what does that tell us about how much time is really needed to reach near-randomness? Does it help us estimate those n squared or one/two n scales they found earlier <ref:2609.13570#pg1>?
Ada: Kolya, the paper says the lower bound in total variation requires a different argument, and that argument is what helps meet their upper bounds. The three lower bounds they derive from their identity argument meet the upper bounds of section three at the same time to establish that cutoff.
Emmy: So, it’s not just one result; it’s a combination where the lower bound derived from algebraic identities matches the upper bound derived from spectral analysis, which pinpoints those specific cutoff scales. That matching is what gives us the final result on the total variation cutoff at n squared with a window of at most root n.
Kolya: It’s interesting how they use this combination to prove that the cutoff is indeed where they expect it to be, rather than just setting an upper bound somewhere else. Does this mean we can trust these cutoffs as reliable estimates for the mixing time?
Paper summary: Ada: They are quite reliable for fixed q greater than one. The paper states that the first limit, which suggests a cutoff at one over two n plus log q n with a window of order one, is open only in the range where time t is between n squared minus some constant times root n and n squared plus this term.
Emmy: That means we have a very specific window for that faster convergence scale. The second limit, which suggests the one over two n plus log q n cutoff with a window of order one they claim is already proven by theorem three point five and corollary three point nine and theorem three point twelve together with theorems five and one point three <ref:2609.13570#pg1>.
Kolya: So we have established that for fixed q greater than one, we know the exact scaling for both the l two cutoff at one over two n plus log q n and the total variation cutoff at n squared with a window of at most root n. What does this tell us about future work?
Ada: The paper seems to conclude by summarizing these results and pointing toward what they expect to happen next, but it doesn't give a huge leap forward in terms of new techniques for mixing times. It solidifies the scaling behavior for these specific walks within this algebraic framework.
Emmy: It provides a very clear roadmap for how researchers might approach studying similar shuffles by looking at their representation theory in the Hecke algebra Hq(Sn). The structure is clearly dictating the mixing speed here.
Kolya: So, to wrap up, for fixed q greater than one, all three chains—the scan, the random-to-random shuffle, and the k-star transposition shuffle—have l two cutoff at one over two n plus log q n with a constant order window. And they have total variation cutoff at n squared with a window of at most root n.
Ada: That’s the main takeaway from this paper on "Cutoff for q-deformed classical card shuffles in the type A Iwahori--Hecke algebra". It establishes these precise convergence rates for these specific shuffling models using spectral analysis of the Hecke algebra.
Emmy: It shows that even though the moves are different, they share a common structural scaling behavior dictated by q greater than one.
Kolya: And as q gets very large, we see a deterministic limit where everything settles into a single inversion-increasing dynamic. That deterministic orbit gives us a lower bound on total variation mixing time.
Ada: That's the picture presented in this paper about these three random walks on Hq(Sn).
Emmy: It connects abstract algebra directly to the concrete performance of shuffling algorithms.
Conclusion: Ada: So we're wrapping up this look at the paper "Cutoff for q-deformed classical card shuffles in the type A Iwahori--Hecke algebra".
Emmy: It’s about three different random walks on a specific Hecke algebra, Hq(Sn).
Kolya: And for fixed q greater than one, they found some very specific stopping points.
Ada: They proved that all three walks—the short systematic scan, the random-to-random shuffle, and the k-star transposition shuffle—have two kinds of cutoffs.
Emmy: One is an l two cutoff happening at one over two n plus log q n with a constant order window.
Kolya: And another is a total variation cutoff at n squared with a window that's at most order root n.
Ada: These results are important because they show that the mixing behavior for these different shuffles, when viewed through this Hecke algebra structure, actually scales in the same way for fixed q greater than one.
Emmy: It suggests there’s a deep structural link between these different shuffling processes that forces their convergence speed to be related by q.
Kolya: What this means practically is that we have some very precise numbers telling us how much time we need before these shuffles are considered mixed in terms of total variation distance.
Ada: It gives us concrete bounds for the mixing time, which is always a big deal when you're trying to build an algorithm.
Emmy: And as q gets really big, all these different walks start behaving like one single deterministic process that just increases inversions.
Kolya: That deterministic limit gives us a lower bound on the total variation mixing time, which is a solid starting point for any practical application.
Ada: So this paper provides these sharp scaling results for fixed q greater than one and shows how the algebra dictates that behavior across different types of shuffles.
Emmy: It sets up a clear framework for studying similar shuffling problems using representation theory in this Hecke algebra setting.
Stony Brook University
math.PR, math.CO, math.RT
Submitted: 2026-09-11
Updated: 2026-11-10
Comments: 38 pages
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 91/100
The gist: We study three random walks of the type A Iwahori–Hecke algebra Hq(Sn) and prove that for fixed q > 1 they exhibit total variation and l2 cutoff at specific scales Chains and Operators The paper…
Key concepts
- Iwahori–Hecke algebra Hq(Sn)
- This is a mathematical structure used to study permutations, specifically related to the symmetric group Sn. It provides the algebraic framework for analyzing the random walks (shuffles) being studied in this paper. It's a sophisticated tool from representation theory.
- L2 Cutoff
- This describes how quickly a random walk converges in terms of its energy or variance (l2 norm). The paper shows that for these specific shuffles, the l2 cutoff occurs at a scale of $1/2n + \log q n$ with a constant-order window, meaning convergence is faster than expected at certain scales.
- Total Variation Cutoff
- This measures the convergence in terms of total variation distance, which is a measure of how close the probability distribution is to its stationary state. The paper finds this cutoff occurs at $n^2$ with a window of at most order $\sqrt{n}$, indicating the mixing time for these processes.
- Mixing Scales
- This refers to the characteristic scales (in terms of n) at which the random walks exhibit their convergence behavior, such as l2 cutoff or total variation cutoff. The paper proves that for fixed q > 1, all three investigated chains share the same mixing scales.
Terminology
Summary
We study three random walks of the type A Iwahori–Hecke algebra Hq(Sn) and prove that for fixed q > 1 they exhibit total variation and l2 cutoff at specific scales
Chains and Operators
The paper investigates three random walks on Hq(Sn): the short systematic scan, the q–random–to–random shuffle, and the q–deformed k–star transposition shuffle All three chains have the Mallows measure as their stationary distribution and can be viewed as combinations of Metropolis moves encoded by elements of Hq(Sn) The transition operators are quite different, but for fixed q > 1 they turn out to have the same mixing scales The short systematic scan is obtained by applying adjacent Metropolis moves successively in one direction and then in reverse The q–deformed k–star transposition shuffle is studied by diagonalizing it using Hecke Jucys–Murphy elements
Spectral Analysis of the Shuffle
The spectrum of the q–deformed k–star transposition shuffle P is analyzed, yielding eigenvalues indexed by standard Young tableaux S The eigenvalue of P indexed by S is given by eigq(S) = 1[n]q + q[n − 1]q[n]q Pk l=1 [n − l]q X k l=1 [cn+1−l(S)] q The connection between these chains already appears before taking any limit, as the short systematic scan and P are affine functions of the same Jucys–Murphy element Jn(q)
Mixing Times and Cutoffs
For fixed q > 1, all three chains exhibit l2 cutoff at 1/2n + logq n with a constant-order window The total variation cutoff is at n squared with a window of at most order √n Specifically, the upper bound for the short systematic scan is improved both in the upper and lower bounds of Diaconis and Ram The total variation cutoff is at n squared with a window of at most order √n
Limiting Dynamics and Lower Bounds
As q → ∞, all three operators collapse to a single deterministic dynamics where the chain performs exactly those swaps which increase the number of inversions The limiting dynamics is deterministic, and its orbit starting from the identity gives the total variation lower bound for all of them The lower bound in total variation requires a different argument and is proved in Section 6
Conclusion on Mixing Scales
The three chains exhibit total variation cutoff at n squared with a window of at most order √n The scale √n appears only in this lower-bound argument The upper bound already gives mixing at n squared + 1/2 logq n + O(1) Conjecture 6.8 suggests the cutoff is at 1/2n + logq n with a window of order 1 The second limit has already been proved: it is Theorem 3. p. 15 (respectively Corollary 3. p. 3 p. 39, Theorem 3. p. 2 p. 212) together with (5) and Theorem 1. p. 1 p. 13
Total Variation Cutoff
The three chains exhibit total variation cutoff at n squared with a window of at most order √n The lower bound in total variation is derived from the identity, which is enough to bound tmix from below The three lower bounds above meet the upper bounds of Section 3 at the same time, which gives us the cutoff
Final Result on Cutoff
The q–deformed k–star transposition shuffle, the q–random–to–random shuffle, and the short systematic scan all exhibit l2 cutoff at 1/2n + logq n with a window of order 1 In particular, by Theorem 4.7, for n ≥ 4, K t id π - 1 TV ≥ q c - 1/2 The three chains exhibit total variation cutoff at n squared with a window of at most order √n
Summary of Results
The paper proves that for fixed q > 1, all three chains exhibit l2 cutoff at 1/2n + logq n with a constant-order window The total variation cutoff is at n squared with a window of at most order √n This result holds for the q–deformed k–star transposition shuffle, the q–random–to–random shuffle, and the short systematic scan The second limit has already been proved: it is Theorem 3.5 (respectively Corollary 3.9, Theorem 3.12) together with (5) and Theorem 1.3 The first is open only in the range n squared - O(√n) ≤ t ≤ n squared + 1/2 logq n
Acknowledgements
We are deeply grateful to Persi Diaconis for many generous and illuminating conversations, from which this work has benefited greatly We also thank our advisor, Evita Nestoridi, for her invaluable guidance throughout this project The first author thanks Colin Defant for useful discussions
References
[1] Samira Arfaee and Bryan Wong. “Cutoff for q-deformed classical card shuffles in the type A Iwahori–Hecke algebra”
[2] Ilani Axelrod-Freed et al. “Spectrum of random-to-random shuffling in the Hecke algebra”
[3] Michael E. Bate, Stephen B. Connor, and Oliver Matheau-Raven. “Cutoff for a onesided transposition shuffle”
[4] Nathana¨el Berestycki and Rick Durrett. “A phase transition in the random transposition random walk”
[5] Megan Bernstein and Evita Nestoridi. “Cutoff for random to random card shuffle”
[6] Anders Bjorner and Francesco Brenti. Combinatorics of Coxeter groups
[7] Sarah Brauner et al. The q-Deformed Random-to-Random Family in the Hecke Algebra
[8] Persi Diaconis. “Applications of noncommutative Fourier analysis to probability problems”
[9] Persi Diaconis. “Mathematical Developments from the Analysis of Riffle Shuffling”
[10] Persi Diaconis and Arun Ram. “Analysis of systematic scan Metropolis algorithms using Iwahori–Hecke algebra techniques”
[11] Persi Diaconis and Laurent Saloff-Coste. “Comparison Techniques for Random Walk on Finite Groups”
[12] Ilani Axelrod-Freed et al. “Random walks on finite groups: a survey of analytic techniques”
[13] Persi Diaconis and Mehrdad Shahshahani. “Generating a random permutation with random transpositions”
[14] A. B. Dieker and F. p. 1 V. Saliola. “Spectral analysis of random-to-random Markov chains”
[15] Richard Dipper and Gordon James. “Representations of Hecke algebras of general linear groups”
[16] Nadia Lafreni´ere. “Eigenvalues of symmetrized shuffling operators”
[17] Tina Li et al. “Demazure Product of Permutations and Hopping”
[18] Peter Matthews. “A strong uniform time for random transpositions”
[19] Ben Morris, Weiyang Ning, and Yuval Peres. “Mixing Time of the Card-Cyclic-toRandom Shuffle”
[20] Elchanan Mossel, Yuval Peres, and Alistair Sinclair. “Shuffling by Semi-Random Transpositions”
[21] G. E. Murphy. “On the Representation Theory of the Symmetric Groups and Associated Hecke Algebras”
[22] Danny Nam and Evita Nestoridi. “Cutoff for the cyclic adjacent transposition shuffle”
[23] P. N. Norton. “0-Hecke algebras”
[24] Chuan Qin and Ben Morris. “Improved Bounds for the Mixing Time of the Randomto-Random Shuffle”
[25] Arun Ram. “Seminormal representations of Weyl groups and Iwahori–Hecke algebras”
[26] Victor Reiner, Franco Saliola, and Volkmar Welker. “Spectra of Symmetrized Shuffling Operators”
[27] Bruce E. Sagan. The symmetric group. p. 1 p. 1 Second
[28] Laurent Saloff-Coste and Jessica Z´u˜niga. “Refined Estimates for Some Basic Random Walks on the Symmetric and Alternating Groups”
[29] Eliran Subag. “A lower bound for the mixing time of the random-to-random insertions shuffle”
[30] Lucas Teyssier. “Limit profile for random transpositions”
[31] Jay-Calvin Uyemura-Reyes. “Random walk, semidirect products, and card shuffling”
[32] Bruce E. Sagan. The symmetric group. Second Vol 203
[38] [This page is not referenced in the text.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve mixing time estimation for card shuffles by utilizing spectral information from diagonalizing q-deformed operators, specifically by using
the spectra of the three chains to study their mixing behavior.
This allows for proving thatall three exhibit total variation and l2 cutoff
with specific bounds like1/2n + logq n
and a window of order 1. -
Enhance the ability to determine starting state sensitivity in Markov chains by leveraging Theorem 1.3, which states that
the identity is in fact the worst starting state in l2,
ensuring that upper bounds derived from the identity holduniformly over all starting states.
-
Develop a method for calculating total variation lower bounds by using the limiting dynamics when q approaches infinity, where
all three operators become the same for every k; see Theorem 5.1,
and comparing this to a deterministic orbit to find thetotal variation lower bound for all of them.
-
Integrate structural properties of Hecke algebras into analysis by using the representation theory framework, specifically utilizing character formulas like
the eigenvalues of P indexed by S is eigq(S) = 1[n]q + q[n − 1]q[n]q Pk l=1 [n − l]q X k l=1 [cn+1−l(S)] q
to bound spectral sums. -
Improve the analysis of the random-to-random shuffle by using its specific eigenvalue formula,
eigq(λ, µ) = Eλ/µ(q) [n]2 q, Eλ/µ(q) = q n X b∈λ/µ c(b) q + Xn r=µ+1 q n−r [r]q,
to establish tighter bounds than those for the k-star transposition shuffle. -
Refine the calculation of mixing times by employing a refined counting argument in total variation bounds, specifically using "Chebyshev’s inequality gives pi(Sn - A) <= Varπ(D) (n-2t 2)−Eπ(D) 2
to show that
Xt id - π TV ≥ 1 − Eπ(D) n-2t squared," leading to the final cutoff result.
Sources
- Shuffling via sums of Jucys--Murphy Elements
- Spectrum of random-to-random shuffling in the Hecke algebra
- Eigenvalues of symmetrized shuffling operators
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves