pith. sign in

arxiv: 2504.07918 · v2 · pith:PMC67G2Snew · submitted 2025-04-10 · 🧮 math.CO · math.PR

Shuffling via sums of Jucys--Murphy Elements

Samira Arfaee , Evita Nestoridi This is my paper

Pith reviewed 2026-05-22 19:56 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords card shufflingmixing timescutoffJucys-Murphy elementssymmetric grouptranspositionsrepresentation theory
0
0 comments X

The pith

The k-star transpositions shuffle exhibits total variation cutoff at exactly fraction times n log n steps.

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

The paper establishes exact mixing times for a family of card shuffles on n cards where each move applies a transposition drawn from the Jucys-Murphy elements of the symmetric group. It focuses on the k-star transpositions shuffle, which interpolates between the classical random transpositions and star transpositions models. Representation theory of the symmetric group is used to compute all eigenvalues of the transition matrix directly from the action of those elements, yielding the second-largest eigenvalue and hence the cutoff location. A sympathetic reader would care because this supplies a precise, parameter-dependent mixing time for an entire interpolation family rather than isolated cases, together with matching limit profiles in the extreme regimes of k.

Core claim

The transition matrices for shuffles generated by sums of Jucys-Murphy elements are diagonalized in the irreducible representations of S_n by the known action of those elements. For the special case of the k-star transpositions shuffle the second-largest eigenvalue produces total-variation cutoff at time (2n-(k+1))/(2(n-1)) n log n with window of size (2n-(k+1))/(2(n-1)) n. In the regimes k/n to 0 or k/n to 1 the limiting profile coincides with the one already known for random transpositions.

What carries the argument

Sums of Jucys-Murphy elements, which generate the allowed transpositions and whose eigenvalues in each irrep of S_n determine the spectrum of the shuffle operator.

If this is right

  • The cutoff time is precisely (2n-(k+1))/(2(n-1)) n log n with window of the same order times n.
  • In the limit k/n to 0 or k/n to 1 the shuffle shares the same limit profile as random transpositions.
  • Eigenvalues of the transition matrices for the whole family of Jucys-Murphy sums are given explicitly by representation theory.
  • The mixing time scales linearly with the coefficient (2n-(k+1))/(2(n-1)), recovering the known random-transpositions time when the coefficient is 1.

Where Pith is reading between the lines

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

  • The same diagonalization technique could be applied to other linear combinations of conjugacy classes that admit simple descriptions in Young-diagram coordinates.
  • The matching limit profiles in the extreme regimes suggest that the cutoff shape is controlled by the largest eigenvalue gap rather than finer details of the generator.
  • One could test whether the cutoff window remains of order n for all fixed ratios k/n by tracking the contribution of the second and third eigenvalues.

Load-bearing premise

The transition operators are diagonalized in the irreducible representations of S_n by the known action of the Jucys-Murphy elements, allowing the second-largest eigenvalue to be read off directly.

What would settle it

An explicit numerical computation of the total-variation distance for moderate n and fixed k after t = (2n-(k+1))/(2(n-1)) n log n steps that remains bounded away from 1/2 would contradict the claimed cutoff location.

read the original abstract

We consider a family of card shuffles of $n$ cards in which the allowed moves involve transpositions corresponding to the Jucys--Murphy elements of the symmetric group $\{S_m\}_{m \leq n}$. We determine the eigenvalues of the corresponding $n! \times n!$ transition matrices of these shuffles and study the mixing times for a special case, the $k$--star transpositions shuffle, a natural interpolation between the random transpositions shuffle, introduced and studied by Diaconis and Shahshahani, and the star transpositions shuffle, introduced and studied by Diaconis. We prove that the $k$--star transpositions shuffle exhibits total variation cutoff at $\frac{2n-(k+1)}{2(n-1)}n\log n$ with a window of $\frac{2n-(k+1)}{2(n-1)}n$. Furthermore, in the regimes $k/n \rightarrow 0$ or $k/n \rightarrow 1$, this shuffle has the same limit profile as random transpositions, which has been fully determined by Teyssier.

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.

Referee Report

0 major / 3 minor

Summary. The paper studies a family of card shuffles on S_n whose transition measures are linear combinations of Jucys-Murphy elements. It derives explicit eigenvalue formulas for the associated n! × n! transition matrices via the Gelfand-Tsetlin bases of the irreducible representations of S_n. For the k-star transpositions shuffle it proves total-variation cutoff at time (2n-(k+1))/(2(n-1)) n log n with window of size (2n-(k+1))/(2(n-1)) n and shows that the limit profile coincides with that of random transpositions when k/n → 0 or k/n → 1.

Significance. The results furnish a clean representation-theoretic interpolation between the random-transpositions shuffle of Diaconis-Shahshahani and the star-transpositions shuffle of Diaconis. The explicit spectral gap and the matching of Teyssier’s limit profile in the two extremal regimes strengthen the understanding of cutoff phenomena for conjugacy-class walks on S_n. The approach via sums of Jucys-Murphy elements is parameter-free once the measure is fixed and yields reproducible eigenvalue expressions.

minor comments (3)
  1. [Abstract] Abstract: the window is written as a multiple of n without an explicit statement that the total-variation distance drops from 1 to 0 inside an interval of that length; a parenthetical clarification would help readers.
  2. [§2] §2: the precise linear combination that defines the k-star measure from the Jucys-Murphy elements J_2 + … + J_k could be displayed as a displayed equation for immediate reference.
  3. [§4] The proof that the second-largest eigenvalue is attained on a specific family of tableaux (used for the cutoff time) is only sketched; a short paragraph listing the partitions that achieve the maximum would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, for highlighting its significance as an interpolation between known shuffles, and for recommending acceptance. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via standard representation theory

full rationale

The paper's central claims follow from the standard fact that Jucys-Murphy elements are simultaneously diagonalized in the Gelfand-Tsetlin bases of the irreducible representations of S_n, with eigenvalues given by sums of contents of Young tableaux. The second-largest eigenvalue of the k-star transposition operator is read off by explicit maximization over non-identity tableaux, after which the cutoff time, window, and limit profile matching are obtained from classical L^2-to-total-variation bounds and comparison with the known random-transpositions case. All load-bearing steps rely on external representation-theoretic results and prior mixing-time analyses by Diaconis-Shahshahani and Teyssier; no parameter is fitted to the target quantity, no self-citation chain is load-bearing, and no quantity is defined in terms of itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The analysis relies on established results from the representation theory of the symmetric group and prior mixing-time analyses without introducing new free parameters or invented entities.

axioms (1)
  • domain assumption Jucys-Murphy elements act diagonally in the irreducible representations of S_n with known eigenvalues
    The paper uses the algebraic properties of Jucys-Murphy elements to determine the eigenvalues of the shuffle transition matrices.

pith-pipeline@v0.9.0 · 5724 in / 1503 out tokens · 106950 ms · 2026-05-22T19:56:44.868690+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Spectrum of random-to-random shuffling in the Hecke algebra

    Ilani Axelrod-Freed et al. “Spectrum of random-to-random shuffling in the Hecke algebra”. In: arXiv preprint arXiv:2407.08644 (2024)

    work page arXiv 2024

  2. [2]

    Cutoff for a one-sided transposition shuffle

    Michael E. Bate, Stephen B. Connor, and Oliver Matheau-Raven. “Cutoff for a one-sided transposition shuffle”. In: The Annals of Applied Probability 31.4 (2021), pp. 1746–1773

    work page 2021

  3. [3]

    A phase transition in the random transposition random walk

    Nathana¨ el Berestycki and Rick Durrett. “A phase transition in the random transposition random walk”. In: Probab. Theory Related Fields 136.2 (2006), pp. 203–233. issn: 0178- 8051,1432-2064

    work page 2006

  4. [4]

    Cutoff for random to random card shuffle

    Megan Bernstein and Evita Nestoridi. “Cutoff for random to random card shuffle”. In: The Annals of Probability 47.5 (2019), pp. 3303–3320

    work page 2019

  5. [5]

    The q-deformed random-to-random family in the Hecke algebra

    Sarah Brauner et al. The q-deformed random-to-random family in the Hecke algebra . 2025

    work page 2025

  6. [6]

    Proof of Aldous’ spectral gap conjecture

    Pietro Caputo, Thomas M. Liggett, and Thomas Richthammer. “Proof of Aldous’ spectral gap conjecture”. In: J. Amer. Math. Soc. 23.3 (2010), pp. 831–851. issn: 0894-0347,1088- 6834

    work page 2010

  7. [7]

    Applications of noncommutative Fourier analysis to probability problems

    Persi Diaconis. “Applications of noncommutative Fourier analysis to probability problems”. In: ´Ecole d’ ´Et´ e de Probabilit´ es de Saint-Flour XV–XVII, 1985–87. Vol. 1362. Lecture Notes in Math. Springer, Berlin, 1988, pp. 51–100

    work page 1985

  8. [8]

    Group representations in probability and statistics

    Persi Diaconis. Group representations in probability and statistics. Vol. 11. Institute of Math- ematical Statistics Lecture Notes—Monograph Series. Institute of Mathematical Statistics, Hayward, CA, 1988, pp. vi+198. isbn: 0-940600-14-5

    work page 1988

  9. [9]

    Generating a random permutation with random transpositions

    Persi Diaconis and Mehrdad Shahshahani. “Generating a random permutation with random transpositions”. In: Z. Wahrsch. Verw. Gebiete 57.2 (1981), pp. 159–179. issn: 0044-3719

    work page 1981

  10. [10]

    Spectral analysis of random-to-random Markov chains

    A. B. Dieker and F. V. Saliola. “Spectral analysis of random-to-random Markov chains”. In: Adv. Math. 323 (2018), pp. 427–485. issn: 0001-8708,1090-2082

    work page 2018

  11. [11]

    Spectral analysis of word statistics

    Chaim Even-Zohar, Tsviqa Lakrec, and Ran J. Tessler. “Spectral analysis of word statistics”. In: S´ em. Lothar. Combin.85B (2021), Art. 81, 12. issn: 1286-4889

    work page 2021

  12. [12]

    Random shuffles and group representations

    L. Flatto, A. M. Odlyzko, and D. B. Wales. “Random shuffles and group representations”. In: Ann. Probab. 13.1 (1985), pp. 154–178. issn: 0091-1798,2168-894X

    work page 1985

  13. [13]

    The one-sided cycle shuffles in the symmetric group algebra

    Darij Grinberg and Nadia Lafreni` ere. “The one-sided cycle shuffles in the symmetric group algebra”. In: Algebr. Comb. 7.2 (2024), pp. 275–326. issn: 2589-5486

    work page 2024

  14. [14]

    Asymptotic formulæ in combinatory analysis [Proc. London Math. Soc. (2) 17 (1918), 75–115]

    G. H. Hardy and S. Ramanujan. “Asymptotic formulæ in combinatory analysis [Proc. London Math. Soc. (2) 17 (1918), 75–115]”. In: Collected papers of Srinivasa Ramanujan . AMS Chelsea Publ., Providence, RI, 2000, pp. 276–309. isbn: 0-8218-2076-1

    work page 1918

  15. [15]

    The interchange process on high-dimensional products

    Jonathan Hermon and Justin Salez. “The interchange process on high-dimensional products”. In: Ann. Appl. Probab. 31.1 (2021), pp. 84–98. issn: 1050-5164,2168-8737

    work page 2021

  16. [16]

    Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion

    Hubert Lacoin. “Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion”. In: Ann. Probab. 44.2 (2016), pp. 1426–1487. issn: 0091-1798,2168-894X

    work page 2016

  17. [17]

    Coupling from the past

    David A. Levin and Yuval Peres. Markov chains and mixing times . Second. With contribu- tions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. American Mathematical Society, Providence, RI, 2017, pp. xvi+447. isbn: 978-1-4704-2962-1

    work page 2017

  18. [18]

    Random Walks on the Symmetric Group: Cutoff for One-sided Trans- position Shuffles

    Oliver Matheau-Raven. “Random Walks on the Symmetric Group: Cutoff for One-sided Trans- position Shuffles”. PhD thesis. University of York, 2020. 23

    work page 2020

  19. [19]

    Comparing limit profiles of reversible Markov chains

    Evita Nestoridi. “Comparing limit profiles of reversible Markov chains”. In: Electronic Jour- nal of Probability 29 (2024), pp. 1–14

    work page 2024

  20. [20]

    The full spectrum of random walks on complete finite d-ary trees

    Evita Nestoridi and Oanh Nguyen. “The full spectrum of random walks on complete finite d-ary trees”. In: Electron. J. Probab. 26 (2021), Paper No. 43, 17. issn: 1083-6489

    work page 2021

  21. [21]

    Mixing times of one-sided k-transposition shuffles

    Evita Nestoridi and Kenneth Peng. “Mixing times of one-sided k-transposition shuffles”. In: submitted (2025)

    work page 2025

  22. [22]

    Bruce E. Sagan. The symmetric group: representations, combinatorial algorithms, and sym- metric functions. Springer Science and Business Media, 2013

    work page 2013

  23. [23]

    A lower bound for the mixing time of the random-to-random insertions shuf- fle

    Eliran Subag. “A lower bound for the mixing time of the random-to-random insertions shuf- fle”. In: Electron. J. Probab. 18 (2013), no. 20, 20. issn: 1083-6489

    work page 2013

  24. [24]

    Limit profile for random transpositions

    Lucas Teyssier. “Limit profile for random transpositions”. In: Ann. Probab. 48.5 (2020), pp. 2323–2343. issn: 0091-1798,2168-894X. 24

    work page 2020