pith. sign in

arxiv: 2605.28770 · v2 · pith:NTQQEPACnew · submitted 2026-05-27 · 🧮 math.PR · math.CO· math.RT

Cutoff profiles for conjugacy invariant random walks on symmetric groups

Lucas Teyssier This is my paper

Pith reviewed 2026-06-29 10:07 UTC · model grok-4.3

classification 🧮 math.PR math.COmath.RT
keywords symmetric groupsrandom walkscutoffconjugacy classescharactersMurnaghan-Nakayama ruleribbon tableauxPoisson profile
0
0 comments X

The pith

Random walks on symmetric groups generated by conjugacy classes with a macroscopic number of fixed points have a Poissonian cutoff profile.

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

The paper proves asymptotic equivalents for characters of finite-level representations of symmetric groups, meaning Young diagrams with all but finitely many boxes in the first row. These equivalents are obtained by counting ribbon tableaux of various types and feeding the counts into the Murnaghan-Nakayama rule. The resulting character estimates imply that conjugacy-invariant random walks whose generating class has a positive fraction of fixed points exhibit a Poissonian cutoff in total variation distance. The same method yields an explicit cutoff profile for the random involution walk and supplies numerical mixing-time estimates for the random transposition walk on a 52-card deck.

Core claim

We prove asymptotic equivalents of characters for finite-level representations of symmetric groups, that is, for Young diagrams which have all but finitely many boxes on their first row. The proofs rely on computing the number of ribbon tableaux of different types, which allows us to estimate characters via the Murnaghan-Nakayama rule. We deduce that random walks on symmetric groups generated by conjugacy classes with a macroscopic number of fixed points have a Poissonian cutoff profile. We also prove that the random involution walk exhibits cutoff and find its cutoff profile.

What carries the argument

Asymptotic character equivalents for finite-level Young diagrams, derived from ribbon-tableaux enumeration under the Murnaghan-Nakayama rule.

If this is right

  • The cutoff window for these walks is of order 1 and the limiting profile is exactly the cumulative distribution function of a Poisson random variable.
  • The random involution walk on the symmetric group has an explicit cutoff time and profile.
  • Concrete numerical bounds on the mixing time of the random transposition walk become available for a standard deck of 52 cards.
  • Any conjugacy class whose cycle type has a macroscopic number of fixed points generates a walk whose mixing behavior is governed by the same Poisson limit.

Where Pith is reading between the lines

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

  • The ribbon-tableaux technique may supply character asymptotics for other families of representations beyond the finite-level case.
  • The Poisson profile suggests that the mixing process can be coupled to a Poisson process of cycle mergers whose rate is determined by the fixed-point density.
  • The same character estimates could be used to study cutoff for walks on other classical groups when analogous finite-level representations are considered.

Load-bearing premise

The asymptotic character formulas obtained by ribbon-tableaux counting remain valid when the Young diagram has only finitely many boxes outside the first row.

What would settle it

A direct numerical computation, for sufficiently large n, of the total-variation distance to stationarity for a conjugacy-class walk whose support has a fixed positive fraction of fixed points, showing deviation from the Poisson cumulative distribution at the predicted cutoff location.

Figures

Figures reproduced from arXiv: 2605.28770 by Lucas Teyssier.

Figure 1
Figure 1. Figure 1: The diagram λ = (37, 10, 6, 3, 2) ⊢ 58 consists of all cells, the sub-diagram µ = (33, 7, 4, 1) ⊢ 45 consists of all gray cells, and the skew diagram ν = λ\µ consists of all white cells. Let us now (upper-)count how many diagrams there are in S(λ, α, µ, s). First, µ is covered by 1 ribbons in a standard way; there are dµ such configurations (independently of the rest of the ribbon configuration). Also, giv… view at source ↗
Figure 2
Figure 2. Figure 2: All possible ribbon coverings of the skew diagram diagram (10, 6, 3, 2)\(7, 4, 1), with weight (2, 2, 2, 3). Colors are redundant. ways to pick si ribbons of length i for each i ≥ 2, this proves that |S(λ, α, µ, s)| ≲r dµ Y i≥2  fi(σ) si  . (2.20) 9 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: All possible ribbon coverings of the diagram (11, 2), for α = (1, 1, 1, 1, 1, 1, 2, 2, 3). The ribbons of size 1 are filled with the numbers from 1 to 6, the first ribbon of size 2 is filled with 7’s, the second is filled with 8’s, and the ribbon of size 3 is filled with 9’s. Colors are redundant. of such a ribbon tableau is 0, and the second claim follows. 2.6 Proofs of Theorem 2.2, Theorem 2.3, and Corol… view at source ↗
Figure 4
Figure 4. Figure 4: All possible ribbon coverings of the diagram (18, 5, 2, 1) ⊢ 26, for α = (1, 1, 1, 1, 1, 10, 11), and for which the ribbons of size 1 cover the subdiagram µ = (4, 1). Colors are redundant. 12 [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Here λ = (14, 7, 7, 5, 1), α = 197 2111 , and β = 1167 1111 . On the left a ribbon tableau T ∈ RT(λ, α) and on the right the ribbon tableau T ∗ ∈ RT(λ, β) obtained by the fragmentation process. Colors are redundant. injective. It follows that |RT(λ, α)| ≤ |RT(λ, β)|. Finally, using that bi ≤ ai for i ≥ 2 and that b1 = a1 + I, we obtain M(β) = max i≥1 b 1/i i ≤ max(a1 + I, max i≥2 a 1/i i )) ≤ I + max i≥1 a… view at source ↗
read the original abstract

We prove asymptotic equivalents of characters for finite-level representations of symmetric groups, that is, for Young diagrams which have all but finitely many boxes on their first row. The proofs rely on computing the number of ribbon tableaux of different types, which allows us to estimate characters via the Murnaghan--Nakayama rule. We deduce that random walks on symmetric groups generated by conjugacy classes with a macroscopic number of fixed points have a Poissonian cutoff profile. We also prove that the random involution walk exhibits cutoff and find its cutoff profile. Finally, we obtain numerics for the random transposition walk on a deck of 52 cards, giving concrete estimates on the question that originally motivated Diaconis and Shahshahani.

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

2 major / 2 minor

Summary. The paper proves asymptotic equivalents for characters of finite-level representations of symmetric groups (Young diagrams with all but finitely many boxes in the first row) by enumerating ribbon tableaux of various types and applying the Murnaghan-Nakayama rule. These character estimates are then used to deduce that conjugacy-class random walks on S_n with a macroscopic number of fixed points exhibit a Poissonian cutoff profile. The manuscript also establishes cutoff and its profile for the random involution walk, and supplies numerical estimates for the random transposition walk on S_52 addressing a question of Diaconis and Shahshahani.

Significance. If the character asymptotics hold with the required uniformity, the results supply explicit Poissonian cutoff profiles rather than mere cutoff existence for a natural family of conjugacy-invariant walks; this strengthens the literature on mixing times for symmetric-group walks. The combinatorial method via ribbon tableaux provides a concrete tool for such estimates, and the S_52 numerics give practical content to a classical motivating question.

major comments (2)
  1. [Section on cutoff profiles for conjugacy-class walks] The deduction of the Poissonian profile in the main theorem on conjugacy-class walks requires not only leading-term character asymptotics but also explicit error bounds that are uniform over the representations whose eigenvalues control the total-variation distance. The abstract-level description of the ribbon-tableaux enumeration does not indicate whether such rates are obtained; without them the passage from character equivalents to the precise profile may not be justified.
  2. [Section on the random involution walk] For the random involution walk, the claimed cutoff profile likewise rests on the same character asymptotics; it is unclear whether the error terms suffice to identify the limiting profile rather than merely establish cutoff existence.
minor comments (2)
  1. [Introduction] Notation for the finite-level representations (e.g., the precise meaning of 'defect' or 'fixed number of boxes off the first row') should be introduced with a short diagram or example before the main theorems.
  2. [Numerical section] The numerical section on the transposition walk would benefit from a brief statement of the Monte-Carlo sample size and convergence criterion used to produce the estimates.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed report and for emphasizing the need for uniform error control in establishing the precise Poissonian profiles. We address the two major comments below, pointing to the explicit bounds already derived in the manuscript.

read point-by-point responses

  1. Referee: [Section on cutoff profiles for conjugacy-class walks] The deduction of the Poissonian profile in the main theorem on conjugacy-class walks requires not only leading-term character asymptotics but also explicit error bounds that are uniform over the representations whose eigenvalues control the total-variation distance. The abstract-level description of the ribbon-tableaux enumeration does not indicate whether such rates are obtained; without them the passage from character equivalents to the precise profile may not be justified.

    Authors: Sections 3 and 4 derive the character asymptotics via explicit enumeration of ribbon tableaux of all types, combined with the Murnaghan-Nakayama rule. The resulting error terms are O(1/n) and uniform over all Young diagrams with a bounded number of boxes outside the first row (the finite-level representations that contribute to the cutoff window). These bounds are obtained by controlling the number of non-vanishing ribbon tableaux of each length and are stated with explicit constants depending only on the fixed level. They are sufficient to show that the contribution of all non-leading eigenvalues to the total-variation distance is o(1) uniformly, which justifies the exact Poissonian profile in Theorem 1.1. A clarifying sentence can be added to the introduction if the referee prefers. revision: partial

  2. Referee: [Section on the random involution walk] For the random involution walk, the claimed cutoff profile likewise rests on the same character asymptotics; it is unclear whether the error terms suffice to identify the limiting profile rather than merely establish cutoff existence.

    Authors: The analysis in Section 5 uses precisely the same uniform O(1/n) character bounds established in Sections 3-4. Because the error is smaller than the gap between the leading eigenvalue and the next ones throughout the cutoff window, the limiting profile is identified exactly (rather than merely shown to exist). The same uniformity argument applies directly to the involution generator. revision: no

Circularity Check

0 steps flagged

No circularity: derivation uses independent combinatorial enumeration

full rationale

The paper establishes asymptotic character equivalents for finite-level representations by enumerating ribbon tableaux of various types and applying the Murnaghan-Nakayama rule. These counts are computed directly from the Young diagram structure and are not defined in terms of the target cutoff profile or any fitted parameters. The Poissonian cutoff profile for conjugacy-class walks is then deduced from the resulting eigenvalue asymptotics. No self-citation chains, ansatzes smuggled via prior work, or renaming of known results appear as load-bearing steps. The argument is self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard facts from representation theory of symmetric groups; no free parameters or invented entities are indicated in the abstract.

axioms (1)
  • standard math Murnaghan-Nakayama rule computes characters via signed counts of ribbon tableaux
    Invoked to estimate characters from ribbon tableau enumeration for finite-level diagrams.

pith-pipeline@v0.9.1-grok · 5643 in / 1115 out tokens · 25235 ms · 2026-06-29T10:07:07.384209+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

40 extracted references · 9 canonical work pages · 3 internal anchors

  1. [1]

    Another conversation with P ersi D iaconis

    David Aldous. Another conversation with P ersi D iaconis. Statist. Sci. , 28(2):269--281, 2013

    2013

  2. [2]

    Shuffling via sums of Jucys--Murphy Elements

    Samira Arfaee and Evita Nestoridi. Shuffling via T ranspositions. Arxiv preprint https://arxiv.org/abs/2504.07918 , 2025+

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  3. [3]

    Representation theory and cycle statistics for random walks on the symmetric group

    Dominic Arcona. Representation theory and cycle statistics for random walks on the symmetric group. Arxiv preprint, available at https://arxiv.org/abs/2512.13969 , 2026+

    work page arXiv 2026

  4. [4]

    Bate, Stephen B

    Michael E. Bate, Stephen B. Connor, and Oliver Matheau-Raven. Cutoff for a one-sided transposition shuffle. Ann. Appl. Probab. , 31(4):1746--1773, 2021

    2021

  5. [5]

    Universality for random surfaces in unconstrained genus

    Thomas Budzinski, Nicolas Curien, and Bram Petri. Universality for random surfaces in unconstrained genus. Electron. J. Combin. , 26(4):Paper No. 4.2, 34, 2019

    2019

  6. [6]

    Trailing the dovetail shuffle to its lair

    Dave Bayer and Persi Diaconis. Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. , 2(2):294--313, 1992

    1992

  7. [7]

    A random walk on the symmetric group generated by random involutions

    Megan Bernstein. A random walk on the symmetric group generated by random involutions. Electron. J. Probab. , 23:Paper No. 26, 28, 2018

    2018

  8. [8]

    Cutoff profile of ASEP on a segment

    Alexey Bufetov and Peter Nejjar. Cutoff profile of ASEP on a segment. Probab. Theory Related Fields , 183(1-2):229--253, 2022

    2022

  9. [9]

    Cutoff for conjugacy-invariant random walks on the permutation group

    Nathanaël Berestycki and Batı S engül. Cutoff for conjugacy-invariant random walks on the permutation group. Probab. Theory Related Fields , 173(3-4):1197--1241, 2019

    2019

  10. [10]

    Mixing times for random k -cycles and coalescence-fragmentation chains

    Nathanaël Berestycki, Oded Schramm, and Ofer Zeitouni. Mixing times for random k -cycles and coalescence-fragmentation chains. Ann. Probab. , 39(5):1815--1843, 2011

    2011

  11. [11]

    A phase transition for repeated averages

    Sourav Chatterjee, Persi Diaconis, Allan Sly, and Lingfu Zhang. A phase transition for repeated averages. Ann. Probab. , 50(1):1--17, 2022

    2022

  12. [12]

    The Cutoff Profile for Random Transpositions on Repeated Cards in the Full Range of Parameters

    Jiahe Chen. The cutoff profile for random transpositions on repeated cards in the full range of parameters. Arxiv preprint https://arxiv.org/abs/2604.23890 , 2026+

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  13. [13]

    Persi Diaconis, R. L. Graham, and J. A. Morrison. Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures Algorithms , 1(1):51--72, 1990

    1990

  14. [14]

    Applications of noncommutative F ourier analysis to probability problems

    Persi Diaconis. Applications of noncommutative F ourier analysis to probability problems. In \'Ecole d'\'Et\'e de P robabilit\'es de S aint- F lour XV -- XVII , 1985--87 , volume 1362 of Lecture Notes in Math. , pages 51--100. Springer, Berlin, 1988

    1985

  15. [15]

    Group representations in probability and statistics , volume 11 of Institute of Mathematical Statistics Lecture Notes---Monograph Series

    Persi Diaconis. Group representations in probability and statistics , volume 11 of Institute of Mathematical Statistics Lecture Notes---Monograph Series . Institute of Mathematical Statistics, Hayward, CA, 1988

    1988

  16. [16]

    Generating a random permutation with random transpositions

    Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete , 57(2):159--179, 1981

    1981

  17. [17]

    Limit Profiles for Separation Distance

    Peter E. Francis and Evita Nestoridi. L imit P rofiles for S eparation D istance. Arxiv preprint https://arxiv.org/abs/2605.19084 , 2026+

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  18. [18]

    Fixed points of non-uniform permutations and representation theory of the symmetric group

    Jason Fulman. Fixed points of non-uniform permutations and representation theory of the symmetric group. Arxiv preprint https://arxiv.org/pdf/2406.12139 , 2024+

    work page arXiv 2024

  19. [19]

    Poisson- D irichlet distribution for random B elyi surfaces

    Alex Gamburd. Poisson- D irichlet distribution for random B elyi surfaces. Ann. Probab. , 34(5):1827--1848, 2006

    2006

  20. [20]

    The random k cycle walk on the symmetric group

    Bob Hough. The random k cycle walk on the symmetric group. Probab. Theory Related Fields , 165(1-2):447--482, 2016

    2016

  21. [21]

    Hitting time mixing for the random transposition walk: V

    Vishesh Jain and Mehtaab Sawhney. Hitting time mixing for the random transposition walk: V. jain, m. sawhney. Probability Theory and Related Fields , pages 1--26, 2026

    2026

  22. [22]

    A product of invariant random permutations has the same small cycle structure as uniform

    Mohamed Slim Kammoun and Myl\`ene Ma\"ida. A product of invariant random permutations has the same small cycle structure as uniform. Electron. Commun. Probab. , 25:Paper No. 57, 14, 2020

    2020

  23. [23]

    The cutoff profile for the simple exclusion process on the circle

    Hubert Lacoin. The cutoff profile for the simple exclusion process on the circle. Ann. Probab. , 44(5):3399--3430, 2016

    2016

  24. [24]

    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 . The Annals of Probability , 44(2):1426 -- 1487, 2016

    2016

  25. [25]

    Characters of symmetric groups: sharp bounds and applications

    Michael Larsen and Aner Shalev. Characters of symmetric groups: sharp bounds and applications. Invent. Math. , 174(3):645--687, 2008

    2008

  26. [26]

    Random walks on the symmetric group generated by conjugacy classes

    Nathan Anton Mikerin Lulov. Random walks on the symmetric group generated by conjugacy classes . ProQuest LLC, Ann Arbor, MI, 1996. Thesis (Ph.D.)--Harvard University

    1996

  27. [27]

    Morales, Igor Pak, and Greta Panova

    Alejandro H. Morales, Igor Pak, and Greta Panova. Hook formulas for skew shapes I . q -analogues and bijections. J. Combin. Theory Ser. A , 154:350--405, 2018

    2018

  28. [28]

    M\"uller and Jan-Christoph Schlage-Puchta

    Thomas W. M\"uller and Jan-Christoph Schlage-Puchta. Character theory of symmetric groups, subgroup growth of F uchsian groups, and random walks. Adv. Math. , 213(2):919--982, 2007

    2007

  29. [29]

    Representation Theory of Symmetric Groups (1st ed.)

    Pierre-Loïc Méliot. Representation Theory of Symmetric Groups (1st ed.) . Chapman and Hall/CRC., 2017

    2017

  30. [30]

    Comparing limit profiles of reversible M arkov chains

    Evita Nestoridi. Comparing limit profiles of reversible M arkov chains. Electron. J. Probab. , 29:Paper No. 58, 14, 2024

    2024

  31. [31]

    Limit profiles for reversible M arkov chains

    Evita Nestoridi and Sam Olesker-Taylor. Limit profiles for reversible M arkov chains. Probab. Theory Related Fields , 182(1-2):157--188, 2022

    2022

  32. [32]

    Cutoff for the biased random transposition shuffle

    Evita Nestoridi and Alan Yan. Cutoff for the biased random transposition shuffle. Arxiv preprint, available at https://arxiv.org/abs/2409.16387 , 2024+

    work page arXiv 2024

  33. [33]

    Limit profile for the bernoulli--laplace urn via diffusions

    Sam Olesker-Taylor and Dominik Schmid. Limit profile for the bernoulli--laplace urn via diffusions. Annals of Applied Probability , 2026

    2026

  34. [34]

    Sharp character bounds and cutoff for symmetric groups

    Sam Olesker-Taylor, Lucas Teyssier, and Paul Thévenin. Sharp character bounds and cutoff for symmetric groups. Arxiv preprint https://arxiv.org/abs/2503.12735 , 2025+

    work page arXiv 2025

  35. [35]

    Upper bound on the characters of the symmetric groups

    Yuval Roichman. Upper bound on the characters of the symmetric groups. Invent. Math. , 125(3):451--485, 1996

    1996

  36. [36]

    Ph\'enom\`ene de cutoff pour certaines marches al\'eatoires sur le groupe sym\'etrique

    Sandrine Roussel. Ph\'enom\`ene de cutoff pour certaines marches al\'eatoires sur le groupe sym\'etrique. Colloq. Math. , 86(1):111--135, 2000

    2000

  37. [37]

    Limit profile for random transpositions

    Lucas Teyssier. Limit profile for random transpositions. Ann. Probab. , 48(5):2323--2343, 2020

    2020

  38. [38]

    Bounds on skew dimensions and characters of symmetric groups via thick hook decompositions

    Lucas Teyssier. Bounds on skew dimensions and characters of symmetric groups via thick hook decompositions. Arxiv preprint https://arxiv.org/abs/2508.06770 , 2025+

    work page arXiv 2025

  39. [39]

    Every cutoff profile is possible

    Lucas Teyssier. Every cutoff profile is possible. Electronic Journal of Probability , 31:1--17, 2026

    2026

  40. [40]

    Characters of symmetric groups: sharp bounds on virtual degrees and the W itten zeta function

    Lucas Teyssier and Paul Thévenin. Characters of symmetric groups: sharp bounds on virtual degrees and the W itten zeta function. Arxiv preprint https://arxiv.org/abs/2411.04347 , 2024+

    work page arXiv 2024