Cutoff profiles for conjugacy invariant random walks on symmetric groups
Lucas Teyssier · 2026
Read Cutoff profiles for conjugacy invariant random walks on symmetric groups by Lucas Teyssier (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28770.txt.
Introduction
Lucas Teyssier proves long-run matches of characters for views of symmetric groups, that is, Young diagrams with all but finitely many boxes on the first row. His proofs count ribbon tableaux of types, gauging them via the Murnaghan-Nakayama rule. He deduces random walks on symmetric groups generated by classes with many fixed points have a Poisson cutoff profile. He proves the random flip walk shows cutoff and finds its profile. Numbers for the random swap walk on a 52-card deck give firm counts on the Diaconis-Shahshahani question.
Catalog record
| CREATOR | Lucas Teyssier |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76661 |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.28770
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cutoff profiles for conjugacy invariant random walks on symmetric groups Lucas Teyssier Abstract We prove asymptotic equivalents for finite-level representations of symmetric groups, that is, for Young diagrams having all but finitely many boxes on their first row. 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. 1 Introduction 1.1 Some history Let n\geq 2 and let {\mathfrak{S}}_{n} be the symmetric group of index n . Given a probability measure \mu on {\mathfrak{S}}_{n} , we refer to the discrete time Markov chain with transition probabilities P(\sigma,\tau)=\mu(\sigma^{-1}\tau) for \sigma,\tau\in{\mathfrak{S}}_{n} as the random walk driven by \mu or \mu -walk . Denote the uniform measure on a finite set S by \textup{Unif}_{S} , and the conjugacy class of transpositions of {\mathfrak{S}}_{n} by {\mathcal{T}} . The \textup{Unif}_{{\mathcal{T}}} -walk (with laziness 1/n ) is a historically important model known as the random transposition shuffle. In terms of card shuffling, this corresponds to picking at each step two cards independently and uniformly at random, and swapping them. The initial problem that emerged at the Bell Laboratories in the 1970’s was to understand how many random transpositions are needed to mix a deck of 52 cards. We refer to the conversation between Aldous and Diaconis [ Ald13 ] for a more detailed history of the problem. After initial attempts relying purely on probability failed, Diaconis and Shahshahani [ DS81 ] solved this problem (asymptotically) using representation theory. They proved that a phase transition, called cutoff, occurs around t_{n}:=\frac{1}{2}n\ln n steps. Essentially, what they proved is that for any \varepsilon\in(0,1) , denoting the distribution of the walk after t steps by \mu_{t} , we have \textup{d}_{\textup{TV}}\left(\mu_{\left\lfloor(1-\varepsilon)t_{n}\right\rfloor},\textup{Unif}_{{\mathfrak{S}}_{n}}\right)\xrightarrow[n\to\infty]{}1\hskip 10.00002pt\text{ and }\hskip 10.00002pt\textup{d}_{\textup{TV}}\left(\mu_{\left\lceil(1+\varepsilon)t_{n}\right\rceil},\textup{Unif}_{{\mathfrak{S}}_{n}}\right)\xrightarrow[n\to\infty]{}0, (1.1) where the total variation distance between two probability measures \mu and \nu on a finite set S is given by \textup{d}_{\textup{TV}}(\mu,\nu)=\frac{1}{2}\sum_{x\in S}|\mu(x)-\nu(x)| . This led to several refinements and generalizations, and in particular to \textup{Unif}_{{\mathcal{C}}} -walks, where {\mathcal{C}} is a conjugacy class: [ Rou00 , BSZ11 ] for conjugacy classes with small support, [ Hou16 , BŞ19 ] for conjugacy classes of support size o(n) , [ Lul96 , LS08 , TT24 ] for fixed point free permutations, [ Roi96 , MSP07 ] for general L^{2} bounds (that are however weaker than cutoff). Recently, in a companion paper, we proved the L^{2} cutoff for all conjugacy classes with \Theta(n) fixed points [ OTTT25 ] . The cutoff result of Diaconis and Shahshahani was also generalized to several models of non-uniform transpositions [ Dia88a , Lac16b , BCMR21 , NY24 , AN25 ] . What happens within the phase transition is also well understood for transpositions. In [ Tey20 ] , we found the cutoff profile : for any a\in{\mathbb{R}} , we have \textup{d}_{\textup{TV}}\left(\mu_{\left\lfloor t_{n}(1+a/\ln n)\right\rfloor},\textup{Unif}_{{\mathfrak{S}}_{n}}\right)\xrightarrow[n\to\infty]{}\textup{d}_{\textup{TV}}\left(\textup{Poiss}(1),\textup{Poiss}\left(1+e^{-a}\right)\right), (1.2) where \textup{Poiss}(\alpha) denotes the Poisson law of parameter \alpha>0 . The convergence in ( 1.2 ) was extended to cycles of length o(n) in [ NOT22 ] , and to models that are not conjugacy invariant, such as star transpositions [ Nes24 ] . Intuitively, the profile involves Poisson laws because the last observable to be mixed is the number of fixed points. This intuition was recently made rigorous for transpositions [ JS26 ] , and generalized to decks with repeated cards [ Che26 ] . The separation profile for transpositions (and for other models) was also recently found [ FN26 ] . Cutoff profiles have also been found in several other contexts: for instance for the hypercube [ DGM90 ] , the riffle shuffle [ BD92 ] , repeated averages [ CDSZ22 ] , the symmetric and asymmetric simple exclusion processes [ Lac16a , BN22 ] . Many other cutoff profiles have been found in the last few years. Recent accounts of the literature on cutoff profiles can be found in [ OTS26 , Tey26 ] . 1.2 Main results The main novelty of the paper consists of Theorems 2.1 and 2.2 , which give precise asymptotics for finite-level characters of symmetric groups. Our main application is Theorem 1.1 , which finds the profile for conjugacy classes whose cycle structure has \Theta(n) fixed points. We defer representation theoretic statements (and in particular those of Theorems 2.1 and 2.2 ) to Section 2 . Given a probability measure \mu on {\mathfrak{S}}_{n} , the distribution of the \mu -walk (started at the identity permutation Id ) after t steps is given by the t -fold convolution product \mu^{*t} , where the convolution product of two functions f,g{\;:\;}{\mathfrak{S}}_{n}\to{\mathbb{R}} is given by (f\ast g)(\sigma)=\sum_{\tau\in{\mathfrak{S}}_{n}}f(\tau)g(\tau^{-1}\sigma) for \sigma\in{\mathfrak{S}}_{n} . Denote the set of conjugacy classes of {\mathfrak{S}}_{n} by {\textup{Conj}}({\mathfrak{S}}_{n}) , and set {\textup{Conj}}^{*}({\mathfrak{S}}_{n})={\textup{Conj}}({\mathfrak{S}}_{n})\backslash\left\{\left\{\textup{Id}\right\}\right\} . If {\mathcal{C}}\in{\textup{Conj}}({\mathfrak{S}}_{n}) , \sigma\in{\mathcal{C}} , and F is a class function, we may write F({\mathcal{C}}) for F(\sigma) ; for instance {\textup{sgn}}({\mathcal{C}}) and {\textup{sgn}}(\sigma) both denote the sign of the permutation \sigma , and for i\geq 1 , f_{i}({\mathcal{C}}) and f_{i}(\sigma) denote the number of i -cycles of \sigma . For {\mathcal{C}}\in{\textup{Conj}}^{*}({\mathfrak{S}}_{n}) such that 1\leq f_{1}({\mathcal{C}})\leq n-1 , we also set t_{{\mathcal{C}}}=\frac{\ln n}{\ln(n/f_{1}({\mathcal{C}}))}. (1.3) Given a conjugacy class {\mathcal{C}} of {\mathfrak{S}}_{n} and an integer t\geq 0 , let {\mathfrak{E}}({\mathcal{C}},t)={\mathfrak{S}}_{n}\backslash{\mathfrak{A}}_{n} if both t and {\mathcal{C}} are odd (meaning for the second one that the sign of {\mathcal{C}} is -1 ), and {\mathfrak{E}}({\mathcal{C}},t)={\mathfrak{A}}_{n} otherwise. In [ OTTT25 ] , we proved that random walks associated to conjugacy classes {\mathcal{C}} with \Theta(n) fixed points have an L^{2} cutoff at t_{\mathcal{C}} . The next statement shows that they furthermore have a Poissonian cutoff profile, as conjectured (for conjugacy classes with o(n) fixed points) in [ Tey20 , Section 1.2] and [ Nes24 , Conjecture 6.1] . Theorem 1.1 . Let \delta>0 . For each n , let {\mathcal{C}}^{(n)}\in{\textup{Conj}}^{*}({\mathfrak{S}}_{n}) . Assume that f_{1}({\mathcal{C}}^{(n)})\geq\delta n for n large enough. Let a\in{\mathbb{R}} . Let S\subset{\mathbb{N}}^{*} and (t_{n})_{n\in S} be a sequence of integers such that t_{n}=t_{{\mathcal{C}}^{(n)}}\left(1+\frac{a+o(1)}{\ln n}\right) . As S\ni n\to\infty , we have \textup{d}_{\textup{TV}}(\textup{Unif}_{{\mathcal{C}}^{(n)}}^{*t_{n}},\textup{Unif}_{{\mathfrak{E}}({{\mathcal{C}}^{(n)}},t_{n})})\to\textup{d}_{\textup{TV}}\left(\textup{Poiss}(1),\textup{Poiss}\left(1+e^{-a}\right)\right). (1.4) Given an even integer n\geq 2 , the random involution walk on {\mathfrak{S}}_{n} with parameter p\in(0,1) is the walk driven by the measure \textup{RI}_{n,p}=\sum_{s=0}^{n/2}\binom{n/2}{s}(1-p)^{s}p^{n/2-s}\textup{Inv}_{n,s}, (1.5) where \textup{Inv}_{n,s} is the uniform measure on permutations of {\mathfrak{S}}_{n} with cycle type [2^{s},1^{n-2s}] , i.e. which are a product of s disjoint transpositions. Bernstein [ Ber18 ] found the order of magnitude of the mixing time for these walks with a lower bound at \log_{1/p}n , and conjectured a cutoff at this time. We prove this conjecture and furthermore find the cutoff profile. Theorem 1.2 . Let p\in(0,1) . Let a\in{\mathbb{R}} . Let S\subset{\mathbb{N}} and (t_{n})_{n\in S} be a sequence of integers such that t_{n}=\frac{\ln n+a+o(1)}{\ln(1/p)} . As S\ni n\to\infty we have \textup{d}_{\textup{TV}}\left(\left(\textup{RI}_{n,p}\right)^{*t_{n}},\textup{Unif}_{{\mathfrak{S}}_{n}}\right)\to\textup{d}_{\textup{TV}}\left(\textup{Poiss}\left(1+e^{-a}\right),\textup{Poiss}(1)\right). (1.6) Finally, we give estimates on the random transposition walk for n=52 . They rely on computers only for elementary computations. This illustrates that using representation theory can give very precise results not only asymptotically, but also for small values of n , and gives concrete estimates on the question at the origin of the study of