The transpose top-\(2\) with random shuffle (J. Theoret. Probab., 2020) is a lazy random walk on the alternating group \(A_n\) generated by \(3\)-cycles
of the form \((\star,n-1,n)\) and \((\star,n,n-1)\). We obtain the limit profile of this random walk by comparing it with the random walk on \(A_n\)
generated by all \(3\)-cycles. Our method employs a non-commutative Fourier analysis analogue of the comparison method introduced by Nestoridi (Electron. J. Probab., 2024). We also give the complete spectrum of alternating
group graph, thus answering a question of Huang and Huang (J. Algebraic Combin., 2019).
The transpose top-\(2\) with random shuffle, introduced by the first named author in 2020 [1], is a lazy simple random walk on
the Cayley graph \(\widetilde{AG}_n\) of the alternating group \(A_n\) with the generating set \(\{(i,n-1,n),(i,n,n-1):1\leq i\leq n-2\}\). We may assume
\(\widetilde{AG}_n\) as the alternating group graph\(AG_n\); because, they are isomorphic (one is obtained from the other by relabelling the vertices). Formally, \(AG_n\) is the Cayley graph of the alternating group \(A_n\) with the generating set \(\{(1,i,2),(1,2,i):3\leq i\leq n\}\). Jwo et al. introduced the alternating
group graph in 1993 [2], afterward the alternating group graph caught considerable attention in computer science and mathematics [3]–[8]. In general, Cayley graphs provide a very natural and a rich framework for the
design and analysis of interconnection networks for parallel computers [9].
As a random walk on the alternating group \(A_n\), the transpose top-\(2\) with random shuffle is driven by the following probability measure (defined on \(A_n\)): \[\label{eq:TT2R95defn} P(\pi)= \begin{cases} \frac{1}{2n-3}&\text{ if }\pi\in \{(i,n-1,n),(i,n,n-1):1\leq i\leq n-2\},\\
\frac{1}{2n-3}&\text{ if }\pi=\mathop{\mathrm{id}},\text{ the identity permutation},\\ 0&\text{ otherwise}. \end{cases}\tag{1}\] The name ‘transpose top-\(2\) with random shuffle’ was given based on
the shuffling algorithm it represents. The random walk model is a lazy variant of the following process: First, the top two cards are transposed. Then, one of these two cards is selected with equal probability, and it is swapped with a randomly chosen
card from the remaining \(n-2\) cards. The transpose top-\(2\) with random shuffle is irreducible and aperiodic [1]; thus, the distribution after \(k\) transitions converges to the stationary distribution as \(k\) goes to infinity. The stationary distribution in this
case is the uniform distribution \(U_{A_n}\) defined on the alternating group \(A_n\) (because this is a simple random walk on a finite connected regular graph). The first named author has
shown that the transpose top-\(2\) with random shuffle exhibits total variation cutoff phenomenon at time \(n\log n\) with a cutoff window of order \(n\)[1]. However, there is no issue in considering \(n\log n+o(n\log n)\) as a cutoff time, thanks to
the definition of the cutoff phenomenon. Throughout this article, we take the cutoff time for the transpose top-\(2\) with random shuffle to be \(\left(n-\frac{3}{2}\right)\log n\) for
simplicity in calculations.
We now outline an intuitive argument to show that \(\left(n-\frac{3}{2}\right)\log n+O(n)\) steps are expected. To illustrate this, consider the following algorithmic process for marking the cards:
Start by marking one card in the deck.
Select an element from \(\{(i,n,n-1),(i,n-1,n),\mathop{\mathrm{id}}:1\leq i\leq n-2\}\) uniformly at random.
\(\mathop{\mathrm{id}}\), then mark the \(n\)th card, and keep the deck unaltered.
\((i,n-1,n)\), then mark the \((n-1)\)th card and then perform the following: First, transpose the \(n\)th and \((n-1)\)th cards, and then swap the \(i\)th and \(n\)th cards.
\((i,n,n-1)\), then mark the \(n\)th card and then perform the following: Transpose the \(n\)th and \((n-1)\)th
cards, and then swap the \(i\)th and \((n-1)\)th cards.
If all the cards are marked, stop. Else, return to (2) and continue.
We observe that the relative order of the marked cards is close to a random even permutation once the cards at positions \(n\) and \((n-1)\) are marked, given knowledge of which cards are
marked and their positions. This can be shown by induction on the number of marked cards in \(\{1, \dots, n-2\}\), utilizing the fact that the deck is permuted only by 3-cycles, which are even permutations. Consequently,
once all cards are marked, the entire deck undergoes a random even permutation.
Additionally, the probability that a card at position \(i\in\{1,\dots,n-2\}\) is marked is \(\frac{2}{2n-3}\). Once a card at position \(i\in\{1,\dots,n-2\}\) is marked, it remains marked forever. After all the other cards have been marked, it takes at most \(O(n)\) additional steps to mark the \(n\)th and \((n-1)\)th cards. Thus, a coupon collector-type argument ensures that all the cards will be marked after approximately \(\left(n - \frac{3}{2}\right) \log n
+ O(n)\) steps.
In this article, we obtain the limit profile for the transpose top-\(2\) with random shuffle.
The cutoff phenomenon of a finite (irreducible and aperiodic) Markov chain ensures the convergence to stationary distribution occurs suddenly over a very short time, known as the cutoff window. In real-world applications, knowing that a random process
exhibits a cutoff can save time and the running costs of associated algorithms. The first mathematical demonstration of the cutoff phenomenon was due to Diaconis and Shahshahani in 1981, who proved it to hold for the random transposition model [10]. During the following years, Diaconis, Aldous, and their collaborators developed the theory in a long series of papers. Now, it has become one of the vast subfields in
probability literature. For a survey on this topic, we refer the reader to the references [11]–[16].
A relatively new direction is that of the limit profile, a function that precisely describes the sharp transition at the cutoff window. The limit profile is known only for a handful number of Markov chains, viz. the random walk on the hypercube [17] (a short argument was recently provided in [18]), the riffle shuffle [19], the asymmetric exclusion process on the segment [20], the simple exclusion process on the cycle [21], the
Bernoulli–Laplace process [22], the projections of random walks on groups [23], random walks on the abelian groups [24], the simple random walk on
Ramanujan graphs [25], and a few random walks (random transposition [26] and star transposition shuffles [27]) on the symmetric group. More recently, Delhaye
obtained a profile result for the quantum unitary group [28]. Teyssier studied the limit profile for the classical random
transposition model [26] (recently, Jain and Sawhney provided an alternative proof of Teyssier’s result in [29]). It has a connection with a magnificent phenomenon in the theory of mixing times, which informally says, “occasionally, certain aspects of a system mix much
faster than the system as a whole" [30], [31], and supports a conjecture of Nathanaël
Berestycki [26]. Afterward, Nestoridi et al. developed some methods to obtain the limit profile further to reversible Markov chains and applied it to some
models [18], [23], [27]. In this article, we provide a Fourier analysis analogue of Nestoridi’s comparison method [27]. Our technique
compares random walks on a finite group. Importantly, our result does not assume simultaneous diagonalizability of the transition matrices; the comparison result is presented in 2. The formal definitions of the cutoff phenomenon and the limit profile will be given in 2.
Now, we recall the definition of the total variation distance between probability measures on a finite set. Let \(\mathcal{P}\) and \(\mathcal{Q}\) be two probability measures on
a finite set \(\Omega\). Then the total variation distance between \(\mathcal{P}\) and \(\mathcal{Q}\), denoted \(\|\mathcal{P}-\mathcal{Q}\|_{\text{TV}}\), is defined by \[\label{eq:TV-def}
\|\mathcal{P}-\mathcal{Q}\|_{\text{TV}}:=\sup_{A\subseteq\Omega}|\mathcal{P}(A)-\mathcal{Q}(A)|=\frac{1}{2}\sum_{\omega\in\Omega}|\mathcal{P}(\omega)-\mathcal{Q}(\omega)|.\tag{2}\] We now state the main result of this paper.
Theorem 1. Let \(c\in\mathbb{R}\), and \(d_{\emph{TV}}\left(\emph{Poi}(1+e^{-c}),\emph{Poi}(1)\right)\) denote the total variation distance between the laws of the
Poisson distributions with parameters \(1+e^{-c}\) and \(1\). Then the limit profile for the transpose top-\(2\) with random shuffle is given by \(d_{\emph{TV}}\left(\emph{Poi}(1+e^{-c}),\emph{Poi}(1)\right)\) for every real number \(c\), i.e., \[\lim_{n\rightarrow\infty}\left\|P^{*\lceil\left(n-\frac{3}{2}\right)\log n+cn\rceil}-U_{A_n}\right\|_{\text{TV}}=d_{\emph{TV}}\left(\emph{Poi}(1+e^{-c}),\emph{Poi}(1)\right),\;c\in\mathbb{R}.\]
Let us recall the random walk on \(A_n\) generated by all \(3\)-cycles in \(A_n\), i.e., it is the random walk on \(A_n\)
driven by the probability measure \(Q\), defined on \(A_n\), as follows: \[\label{eq:3-cycle95defn} Q(\pi)=
\begin{cases} \frac{3}{n(n-1)(n-2)}&\text{ if }\pi\text{ is a }3\text{-cycle in }A_n,\\ 0&\text{ otherwise}. \end{cases}\tag{3}\] The random walk on \(A_n\) generated by all \(3\)-cycles satisfies the cutoff phenomenon with time \(\frac{n}{3}\log n\) and window \(O(n)\). The limit profile of this random walk is \(d_{\text{TV}}\left(\text{Poi}(1+e^{-c}),\text{Poi}(1)\right)\), thanks to Nestoridi and Olesker-Taylor [18]. We prove 1 by comparing the transpose top-\(2\) with random shuffle and the random walk on \(A_n\) generated by all the
\(3\)-cycles. We conclude this section by giving the organisation of this article.
In 2, we focus on the random walks on a finite group and provide our comparison method, which relies on the Fourier analysis of the group. In 3, we recall the necessary representation
theory of \(A_n\) and lay the ground work for proving 1. Finally, we prove 1 in 4. On a purely graph-theoretic note, we will answer a question asked by Huang and Huang [4] in 5. Finally, in 6, we present an example illustrating our comparison method for non-commuting transition matrices.
2 Comparison of limit profiles for random walks on a finite group↩︎
In this section, we give a method for comparing the limit profiles for various random walks on a finite group. We briefly recall the random walks on a finite group and the representation theory of the group. Then, the main result of this section will be
proved. We end this section with some remarks on our comparison technique.
Let \(G\) be a finite group, and \(\gamma\) be a probability measure on \(G\). Then, the (left-invariant) random walk on \(G\) driven by \(\gamma\) is a time homogeneous (discrete-time) Markov chain \(\{X_t\}_{t=0}^{\infty}\) with state space \(G\) and one-step transition probabilities \[\mathbb{P}\left(X_1=y\mid X_0=x\right):=\gamma(x^{-1}y),\text{ for all }x,y\in G.\] Fix an initial distribution \(\gamma_0\). Let \(\{Y_0,Y_1,Y_2,Y_3,\dots\}\) be a sequence of independent \(G\)-valued random variables such that \(Y_0\) has
law \(\gamma_0\) and \(Y_1,Y_2,Y_3,\dots\) have identical law \(\gamma\). Then, the left-invariant random walk defined above can be obtained as
\[\label{eq:rwfg-def} X_k:=Y_0Y_1Y_2\dots Y_k\text{ for all }k\geq 1.\tag{4}\] Given the initial law \(\gamma_0\), the distribution after
\(k\) transitions is given by the law of \(X_k\). The law of \(X_k\) is given by \(\gamma_0*\gamma^{*k}\), where \(\gamma^{*k}\) is the \(k\)-fold self-convolution of \(\gamma\). Recall that the convolution of two real valued functions \(\alpha\) and \(\beta\) (defined on \(G\)), denoted \(\alpha*\beta\), is defined by \[\alpha*\beta(x):=\sum_{g\in G}\alpha(g)\beta(g^{-1}x)\text{ for all }x\in G.\] The uniform measure \(U_G\) given by \(U_G(g)=\frac{1}{|G|}\) satisfies \(U_G=U_G*\gamma\); thus, it is a stationary distribution of the random walk on \(G\) driven by \(\gamma\). Stationary distribution is unique when the random walk
is irreducible. The random walk on \(G\) driven by the probability measure \(\gamma\) is irreducible if and only if the support of \(\gamma\), i.e., the
set \(\{x\in G:\gamma(x)>0\}\), generates the group \(G\)[16]. Moreover, if the random walk is
aperiodic then the law of \(X_k\) converges to the stationary distribution \(U_G\) as \(k\rightarrow\infty\). The random walk \(\{X_t\}_{t=0}^{\infty}\) is reversible if and only if \(\gamma(g)=\gamma(g^{-1})\) for all \(g\in G\). For any \(x\in G\), let
\(\delta_x\) be the probability measure on \(G\) that takes value \(1\) at \(x\) and \(0\)
elsewhere. Then, we have the following: \[\|\delta_x*\gamma^{*k}-U_G\|_{\text{TV}}=\|\delta_y*\gamma^{*k}-U_G\|_{\text{TV}}\text{ for all }x,y\in G.\] For an irreducible and aperiodic random walk on the group \(G\) driven by the probability measure \(\gamma\), the (total variation) mixing time is a measure of the number of transitions required for the random walk to approach \(U_G\) up to a given tolerance. More formally, given \(\varepsilon>0\), the \(\varepsilon\)-mixing time, denoted \(t_{\text{mix}}(\varepsilon)\), is defined by \[t_{\text{mix}}(\varepsilon):=\min\{k:\|\gamma^{*k}-U_G\|_{\text{TV}}<\varepsilon\}.\]
Now, we are in a position to define the cutoff phenomenon and limit profile; both of these concepts are defined for a sequence of random walks.
Definition 1. Let \(\{G_n\}_n\) be a sequence of finite groups. For each \(n\geq1\), let \(\gamma_n\) be a probability measure defined on
\(G_n\) such that the random walk on \(G_n\) driven by \(\gamma_n\) is irreducible and aperiodic. The sequence is said to satisfy the total variation
cutoff phenomenon if there are sequences \(\{\tau_n\}_n\) (cutoff time) and \(\{w_n\}_n\) (cutoff window) such that \(\tau_n\rightarrow\infty\), \(w_n=o(\tau_n)\), and the following holds: \[\lim_{c\rightarrow-\infty}\liminf_{n\rightarrow\infty}\|\gamma_n^{*\lceil\tau_n+cw_n\rceil}-U_G\|_{\text{TV}}=1,
\,\,\lim_{c\rightarrow\infty}\limsup_{n\rightarrow\infty}\|\gamma_n^{*\lceil\tau_n+cw_n\rceil}-U_G\|_{\text{TV}}=0.\] The (total variation) limit profile can be formally defined as a function \(f:\mathbb{R}\rightarrow\mathbb{ R}\) such that \[\label{eq:limit95profile-def}
f(c):=\lim_{n\rightarrow\infty}\|\gamma_n^{*\lceil\tau_n+cw_n\rceil}-U_G\|_{\text{TV}},\tag{5}\] provided the limit exists for each (fixed) real number \(c\). In case, the limit does not exist, similar
definition could be given for the \(\limsup\) and \(\liminf\).
Remark 1. Given a sequence of irreducible and aperiodic Markov chains, if we denote the \(\varepsilon\)-mixing time of the \(n\)th chain by \(t^{(n)}_{\text{mix}}(\varepsilon)\), then the usual definition of the cutoff phenomenon says \(t^{(n)}_{\text{mix}}(\varepsilon)\rightarrow\infty\) and \(\displaystyle\lim_{n\rightarrow\infty} t^{(n)}_{\text{mix}}(1-\varepsilon)/t^{(n)}_{\text{mix}}(\varepsilon)=1\) for all \(0<\varepsilon<1\). 1 presents an equivalent definition of the cutoff phenomenon.
We now focus on the representation theory of finite groups. Let \(V\) be a finite-dimensional complex vector space and GL\((V)\) be the group of all invertible linear operators on \(V\). Let \(G\) be a finite group. Let \(I\) denote the identity element of GL\((V)\) (i.e. the identity operator on \(V\)) and \(\mathop{\mathrm{e}}\) denote the identity element of \(G\). A (complex) linear representation\((\rho,V)\)
of \(G\) is a homomorphism \(\rho:G\rightarrow \text{GL}(V)\). In particular, \(\rho(\mathop{\mathrm{e}})=I\) and \(\rho(g^{-1})=\rho(g)^{-1},\;g\in G\). The dimension of the vector space \(V\) is said to be the dimension of the representation \(\rho\) and is denoted
by \(d_{\rho}\). The representation space \(V\) is called the \(G\)-module corresponding to the representation \(\rho\). Given \(\rho\), we simply say \(V\) is a representation of \(G\). For example, let \(V\) be one-dimensional. Then, \(\mathop{\mathrm{triv}}:G\rightarrow \text{GL}(V)\), defined by \(\mathop{\mathrm{triv}}(g)\mapsto(v\mapsto v)\), for all \(v\in V\) and \(g\in G\), is a representation of \(G\), known as the trivial representation of \(G\). We now define the
right regular representation of \(G\).
Definition 2. Let \(\mathbb{C}[G]\) be the group algebra consisting of all formal linear combinations of the elements of \(G\) with complex coefficients, i.e. \(\mathbb{C}[G]=\{\sum_{g}c_gg\mid c_g\in\mathbb{C},\; g\in G\}\). Then the right regular representation\(R:G\longrightarrow \text{GL}(\mathbb{C}[G])\) of \(G\) is defined by \[R(g)\left(\displaystyle \sum_{h\in G}C_hh\right)=\displaystyle\sum_{h\in G}C_hhg^{-1},\quad C_h\in\mathbb{C},\] i.e., \(R(g)\) is an
invertible matrix over \(\mathbb{C}\) of order \(|G|\times|G|\).
For \(g\in G\), the trace of the matrix \(\rho(g)\) is said to be the character value of \(\rho\) at \(g\) and
is denoted by \(\chi^{\rho}(g)\). The character values are constants on conjugacy classes, i.e., the characters are class functions. We also have \(\chi^{\rho}(\mathop{\mathrm{e}})=d_{\rho}\), and \(\chi^{\rho}(g^{-1})=\overline{\chi^{\rho}(g)}\), the complex conjugate of \(\chi^{\rho}(g)\). A vector
subspace \(W\) of \(V\) is said to be stable (or invariant) under \(\rho\) if \(\rho(g)\left(W\right)\subset
W\) for all \(g\) in \(G\). If \(W\) is a stable subspace of \(V\) under \(\rho\), then there exists a complement \(W^0\) of \(W\) in \(V\) which is stable under \(\rho\) ([32]). The representation \(\rho\) is irreducible if \(V\) has no non-trivial proper stable subspace. For example the trivial representation defined above is irreducible. Two representations \((\rho_1,V_1)\) and \((\rho_2,V_2)\) of \(G\) are are said to be isomorphic if there exists an invertible linear map \(T:V_1\rightarrow V_2\) such that \(T\circ\rho_1(g)=\rho_2(g)\circ T\) for all \(g\in G\). Schur’s lemma says that If a group algebra element \(\mathfrak{g}\in\mathbb{C}[G]\) commutes with
every element of the group \(G\), then \(\mathfrak{g}\) acts as a scalar on the irreducible \(G\)-modules[32]. We denote the set of all (non-isomorphic) irreducible representations of \(G\) using notation \(\widehat{G}\). The right regular
representation of \(G\) decomposes into irreducible representations with multiplicity equal to their respective dimensions[32]. Thus we have the following: \[\label{eq:Group95alg4695decom46}
\mathbb{C}[G]\cong\underset{\rho\in\widehat{G}}{\oplus}\;d_{\rho}V^{\rho},\tag{6}\] where \(V^{\rho}\) is the irreducible \(G\)-module corresponding to \(\rho\in\widehat{G}\) with dimension \(d_{\rho}\). We also have \(\displaystyle\sum_{\rho\in\widehat{G}}d_{\rho}^2=|G|\) by equating the dimensions in 6 .
We now define the Fourier transform of a real valued function on \(G\). Let \(\phi:G\rightarrow\mathbb{R}\) be a function and \((\rho,V)\) be a
representation of \(G\). Then, the Fourier transform of \(\phi\) at \(\rho\), denoted \(\widehat{\phi}(\rho)\), is
defined as an operator on \(V\) given by \[\widehat{\phi}(\rho):=\sum_{g\in G}\phi(g)\rho(g).\] Given two functions \(\phi,\psi:G\rightarrow \mathbb{R}\),
we have \(\widehat{\phi*\psi}(\rho)=\widehat{\phi}(\rho)\circ\widehat{\psi}(\rho)\), here \(\circ\) denotes the composition of operators. If an ordered basis of \(V\) is understood from the context, then we simply think \(\widehat{\phi}(\rho)\) and \(\widehat{\psi}(\rho)\) as matrices with respect to the basis. In that
case \(\circ\) is the matrix multiplication. We now recall the Plancherel formula [13] below.
\[\label{eq:Plancherel32formula} \sum_{x\in
G}\phi(x^{-1})\psi(x)=\frac{1}{|G|}\sum_{\rho\in\widehat{G}}d_{\rho}\mathop{\mathrm{trace}}\left(\widehat{\phi}(\rho)\widehat{\psi}(\rho)\right).\tag{7}\] For a random walk on \(G\) driven by the probability
measure \(\gamma\) (defined on the group \(G\)), the transition matrix is given by \(\widehat{\gamma}(R)\). Here \(R\) is
the right regular representation defined above. Now, we introduce our comparison method; the main result of this section is given below.
Theorem 2. Let \(\{G_n\}_{n=1}^{\infty}\) be a sequence of finite groups. For each \(n\geq 1\), let \(\nu_n\) and \(\mu_n\) be two probability measures defined on \(G_n\) such that the random walks on \(G_n\) driven by them are irreducible, aperiodic, and reversible. Assume
that the random walk on \(G_n\) driven by \(\nu_n\) satisfies cutoff phenomenon at time \(\tau_{\nu,n}\) with window of order \(w_{\nu,n}\), and it has limit profile \[\label{eq:hypo1}
f(c):=\lim_{n\rightarrow\infty}\left\|\nu_n^{*\lceil\tau_{\nu,n}+cw_{\nu,n}\rceil}-U_{G_n}\right\|_{\emph{TV}},\quad\text{for all }c\in\mathbb{R}.\qquad{(1)}\] If there exist real numbers \(\tau_{\mu,n}\) and
\(w_{\mu,n}\) such that \(w_{\mu,n}=o\left(\tau_{\mu,n}\right)\) and \[\label{eq:hypo2} \lim_{n\rightarrow\infty} \sum_{\rho\in\widehat{G}}
d_{\rho} \mathop{\mathrm{trace}}\left(\left(\widehat{\nu_n}(\rho)\right)^{\lceil\tau_{\nu,n}+cw_{\nu,n}\rceil}-\left(\widehat{\mu_n}(\rho)\right)^{\lceil\tau_{\mu,n}+cw_{\mu,n}\rceil}\right)^2=0,\qquad{(2)}\] then the random walk on \(G_n\) driven by \(\mu_n\) exhibits cutoff phenomenon at time \(\tau_{\mu,n}\) with a window of order \(w_{\mu,n}\); moreover,
its limit profile is given by \(f(c)\).
Proof. We first note that the measures \(\nu_n\) and \(\mu_n\) are symmetric, i.e., \(\nu_n(g)=\nu_n(g^{-1})\) and \(\mu_n(g)=\mu_n(g^{-1})\) for all \(g\in G_n\), because the random walks on \(G_n\) driven by \(\mu_n\) and \(\nu_n\) are both reversible, and the stationary distribution is the uniform distribution on \(G_n\). More precisely, \[U_{G_n}(\mathop{\mathrm{e}})\;\;\times\;\;\text{\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/gfnkidyc.png}\tag{8}\end{figure}}\;\;=\;\;U_{G_n}(g)\;\;\times\;\;\text{\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/dwsatgqb.png}\tag{9}\end{figure}}\;,\]
for all \(g\in G_n\). Here, \(e\) denotes the identity element of \(G_n\).
Let \(c\in\mathbb{R}\). Throughout the proof we write \(\tau_{\nu,n}+cw_{\nu,n}\) as \(t_{\nu}\), and \(\tau_{\mu,n}+cw_{\mu,n}\) as \(t_{\mu}\) to avoid notational complication. Now we have that \[\begin{align}
\label{eq:comparison95method1} &\Big|\left\|\nu_n^{*\lceil t_{\nu}\rceil}-U_{G_n}\right\|_{\text{TV}}-\left\|\mu_n^{*\lceil t_{\mu}\rceil}-U_{G_n}\right\|_{\text{TV}}\Big|\nonumber\\ =\;&\Big|\frac{1}{2}\sum_{g\in G_n}\left(\left|\nu_n^{*\lceil
t_{\nu}\rceil}(g)-U_{G_n}(g)\right|-\left|\mu_n^{*\lceil t_{\mu}\rceil}(g)-U_{G_n}(g)\right|\right)\Big|,\text{ from definition \eqref{eq:TV-def}}\nonumber\\ \leq\;&\frac{1}{2}\sum_{g\in G_n}\Big|\left|\nu_n^{*\lceil
t_{\nu}\rceil}(g)-U_{G_n}(g)\right|-\left|\mu_n^{*\lceil t_{\mu}\rceil}(g)-U_{G_n}(g)\right|\Big|,\text{ by triangle inequality}\nonumber\\ \leq\;&\frac{1}{2}\sum_{g\in G_n}\Big|\left(\nu_n^{*\lceil
t_{\nu}\rceil}(g)-U_{G_n}(g)\right)-\left(\mu_n^{*\lceil t_{\mu}\rceil}(g)-U_{G_n}(g)\right)\Big|,\text{ using triangle inequality}\nonumber\\ =\;&\frac{1}{2}\sum_{g\in G_n}\Big|\nu_n^{*\lceil t_{\nu}\rceil}(g)-\mu_n^{*\lceil
t_{\mu}\rceil}(g)\Big|\leq\;\frac{1}{2}\;\sqrt{\sum_{g\in G_n}|G_n|\left(\nu_n^{*\lceil t_{\nu}\rceil}(g)-\mu_n^{*\lceil t_{\mu}\rceil}(g)\right)^2},
\end{align}\tag{10}\] where the inequality in 10 follows from Cauchy–Schwarz inequality. For every \(g\in G_n\), let us set \[\eta_n(g):=\nu_n^{*\lceil t_{\nu}\rceil}(g)-\mu_n^{*\lceil t_{\mu}\rceil}(g).\] The self-convolution of a symmetric measure is symmetric; therefore, \(\eta_n(g)=\eta_n(g^{-1})\) for all \(g\in G\). Thus, the Plancherel formula 7 and 10 implies \[\begin{align} \Big|\left\|\nu_n^{*\lceil
t_{\nu}\rceil}-U_{G_n}\right\|_{\text{TV}}-\left\|\mu_n^{*\lceil t_{\mu}\rceil}-U_{G_n}\right\|_{\text{TV}}\Big|^{2}\leq\;&\frac{1}{4}\sum_{\rho\in \widehat{G}_n} d_{\rho} \mathop{\mathrm{trace}}\left(\widehat{\eta}_n(\rho)\right)^2 \nonumber\\
=&\frac{1}{4}\sum_{\rho\in \widehat{G}_n} d_{\rho} \mathop{\mathrm{trace}}\left(\widehat{\nu_n^{*\lceil t_{\nu}\rceil}}(\rho)-\widehat{\mu_n^{*\lceil t_{\mu}\rceil}}(\rho)\right)^2 \tag{11}\\ =&\frac{1}{4}\sum_{\rho\in \widehat{G}_n} d_{\rho}
\mathop{\mathrm{trace}}\left(\left(\widehat{\nu_n}(\rho)\right)^{\lceil t_{\nu}\rceil}-\left(\widehat{\mu_n}(\rho)\right)^{\lceil t_{\mu}\rceil}\right)^2.\tag{12}\;
\end{align}\] The equality in 11 follows from the fact \(\widehat{\eta}_n(\rho)=\widehat{\nu_n^{*\lceil t_{\nu}\rceil}}(\rho)-\widehat{\mu_n^{*\lceil t_{\mu}\rceil}}(\rho)\) for all \(\rho\in \widehat{G}_n\). Now, letting \(n\rightarrow\infty\) in 12 , the hypotheses ?? and ?? implies \[\label{eq:comparison95method}
\lim_{n\rightarrow\infty}\left\|\mu_n^{*\lceil\tau_{\mu,n}+cw_{\mu,n}\rceil}-U_{G_n}\right\|_{\emph{TV}}=f(c),\quad c\in\mathbb{R}.\tag{13}\] The cutoff phenomenon of the random walk on \(G_n\) driven by \(\nu_n\) ensures \[\lim_{c\rightarrow-\infty}f(c)=1\text{ and }\lim_{c\rightarrow\infty}f(c)=0.\] Thus, the theorem follows from 13 . ◻
Remark 2. For the case of random walks on a finite group, 2 is the Fourier analysis analogue of Nestoridi’s comparison technique [27]. It is useful when the random walks are defined on a group that only has irreducible representations of ‘small’ dimensions (viz. the dihedral
group). It is also useful when the transition matrices are simultaneously block-diagonalizable with blocks of ‘small’ size. In 6, we will demonstrate our comparison method (2) for the latter case, with each block size at most \(2\).
The main goal of this section is to prepare the platform for the proof of 1. We recall the spectrum of the transition matrices for two random walks on \(A_n\) driven by \(P\) and \(Q\). Let us first define some combinatorial objects that will be used for the rest of this paper.
Let \(n\) be a positive integer. A partition of \(n\), denoted \(\lambda:=(\lambda_1,\cdots,\lambda_r)\vdash n\), is defined as a weakly
decreasing sequence \((\lambda_1,\cdots,\lambda_r)\) of positive integers such that \(\sum_{i=1}^{r}\lambda_i=n\). The partition \(\lambda\) can be
pictorially visualised using its Young diagram. The Young diagram of \(\lambda\) is a left-justified arrangement of \(r\) rows of boxes with \(\lambda_i\) boxes in the \(i^{\text{th}}\) row. For example there are five partitions of the positive integer \(4\) viz. (4), (3,1), (2,2), (2,1,1) and
(1,1,1,1), and the corresponding Young diagrams are given in Figure 1.
None
Figure 1: Young diagrams with \(4\) boxes..
The Young tableaux of shape \(\lambda\) or simply \(\lambda\)-tableaux, are obtained by filling the numbers \(1,\dots,n\) in the boxes
of the Young diagram of \(\lambda\). A \(\lambda\)-tableau is standard if the entries in its boxes increase from left to right along rows and from top to bottom along columns. The
set of all standard tableaux of a given shape \(\lambda\) is denoted by \(\mathop{\mathrm{Std(\lambda)}}\). For example, the standard Young tableaux of shape \((3,1)\) are listed in Figure 2. We write \(d_{\lambda}\) to denote the number of standard Young tableaux of shape \(\lambda\).
None
Figure 2: Standard Young tableaux of shape \((3,1)\)..
The content of a box in row \(u\) and column \(v\) of a diagram is the integer \(v-u\). Given a tableau \(T\in\mathop{\mathrm{Std(\lambda)}}\), let \(b_T(i)\) denote the box in \(T\) containing the integer \(i\) and its content is
denoted by \(c(b_T(i))\) for \(1\leq i\leq n\). For example, \(c(b_{T_1}(1))=0,c(b_{T_1}(2))=1,c(b_{T_1}(3))=2,c(b_{T_1}(4))=-1\) for the standard Young
tableau \(T_1\) given in Figure 2. The conjugate the Young diagram \(\lambda\), denoted \(\lambda^{\prime}\), is obtained by reflecting \(\lambda\) with respect to the diagonal consisting of boxes with content \(0\). A diagram \(\lambda\) is self-conjugate if \(\lambda^{\prime}=\lambda\). An upper standard Young tableau of shape \(\lambda\) is a standard Young tableau
\(T\) such that \(c(b_T(2))=1\). For example, \(T_1\) and \(T_2\) in Figure 2 are the upper standard Young tableau of shape \((3,1)\). The collection of all upper standard tableaux of shape \(\lambda\) is denoted by
\(\mathop{\mathrm{UStd(\lambda)}}\). From now on, we denote the cardinality of a (given) set \(S\) by \(|S|\). A counting argument (see a related discussion
in [1]) gives \[\label{eq:Ustd-count} \begin{cases}
&|\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}|=|\mathop{\mathrm{Std(\lambda)}}|=d_{\lambda},\;\text{ for non-self-conjugate }\lambda\vdash n, \text{ and }\\ &d_{\lambda}^+ =d_{\lambda}^-:=
|\mathop{\mathrm{UStd(\lambda)}}|=\;\frac{1}{2}|\mathop{\mathrm{Std(\lambda)}}|=d_{\lambda}/2,\; \text{ for self-conjugate }\lambda\vdash n. \end{cases}\tag{14}\] Let \(\mathop{\mathrm{Par(n)}}\) denote the
set of all partitions of \(n\). We now define two subsets \(\mathop{\mathrm{CPar(n)}}\) and \(\mathop{\mathrm{NCPar(n)}}\) of \(\mathop{\mathrm{Par(n)}}\) as follows: \[\begin{align} \mathop{\mathrm{CPar(n)}}&=\{\lambda\in\mathop{\mathrm{Par(n)}}\mid\lambda=\lambda^{\prime}\},\;\text{ and }\\
\mathop{\mathrm{NCPar(n)}}&=\{\lambda\in\mathop{\mathrm{Par(n)}}|\lambda\neq\lambda^{\prime}\text{ and }\lambda_i>\lambda'_i, \text{ here }i\text{ is the smallest index satisfying }\lambda_i\neq \lambda'_i\},
\end{align}\] i.e., \(\mathop{\mathrm{NCPar(n)}}\) consists of the ‘fat’ non-self-conjugate partitions of \(n\) and \(\mathop{\mathrm{CPar(n)}}\)
consists of all self-conjugate partitions of \(n\). For example, see Figure 3 (recall Par\((4)\) from Figure 1).
None
Figure 3: Example of \(\text{CPar}(4)\) and \(\text{NCPar}(4)\)..
We now briefly recall the representation theory of \(A_n\), for more details we refer the the book of James and Kerber [33]. For
every non-self-conjugate partition \(\lambda\) of \(n\), there is an irreducible representation of \(A_n\); we denote the corresponding irreducible \(A_n\)-module by \(D_{\lambda}\). The dimension of \(D_{\lambda}\) is \(d_{\lambda}\); moreover, \(D_{\lambda}\) and \(D_{\lambda'}\) are isomorphic for all non-self-conjugate \(\lambda\vdash n\). For each self-conjugate partition \(\lambda\) of \(n\), there are two non-isomorphic irreducible representations \(D^+_{\lambda}\) and \(D^-_{\lambda}\) of \(A_n\). The dimension of \(D^+_{\lambda}\) (respectively, \(D^-_{\lambda}\)) is \(d_{\lambda}^+\) (respectively, \(d_{\lambda}^-\)) for every \(\lambda\in\mathop{\mathrm{CPar(n)}}\). Therefore, the set of all irreducible \(A_n\)-module is given by
\[\label{eq:irr-A95n-module}
\big\{D_{\lambda}:\lambda\in\mathop{\mathrm{NCPar(n)}}\big\}\bigcup\big\{D^+_{\lambda},D^-_{\lambda}:\lambda\in\mathop{\mathrm{CPar(n)}}\big\}.\tag{15}\]
Now, recall \(P\) from 1 . The eigenvalues of \(\widehat{P}(\lambda),\lambda\in\mathop{\mathrm{NCPar(n)}}\) can be obtained from [1], and eigenvalues of \(\widehat{P}(\lambda^{\pm}),\lambda\in\mathop{\mathrm{CPar(n)}}\) can be obtained from [1]. Here, we write \(\lambda^+\) (respectively, \(\lambda^-\)) to denote the index for the irreducible representation
\(D^+_{\lambda}\) (respectively, \(D^-_{\lambda}\)). More formally, we have the following.
Lemma 3. For a non-self-conjugate \(\lambda\vdash n\), the eigenvalues of \(\widehat{P}(\lambda)\) are indexed by the set \(\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\). For self-conjugate \(\lambda\vdash n\), \(\widehat{P}(\lambda^+)\) and \(\widehat{P}(\lambda^-)\) have the same spectrum, and the eigenvalues of \(\widehat{P}(\lambda^{\pm})\) are indexed by the set \(\mathop{\mathrm{UStd(\lambda)}}\)1. Let \(\lambda\vdash n\); suppose \(\mathcal{E}_T\) denote the eigenvalue indexed by \(T\in \mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\).
If \(n-1\) and \(n\) appear in the same row of \(T\), then \(\mathcal{E}_T=\frac{c(b_T(n))+c(b_T(n-1))}{2n-3}\).
If \(n-1\) and \(n\) appear in the same column of \(T\), then \(\mathcal{E}_T=-\frac{c(b_T(n))+c(b_T(n-1))}{2n-3}\).
If \(n-1\) and \(n\) appear neither in the same row nor in the same row of \(T\), then \[\begin{cases}
\mathcal{E}_T=\frac{c(b_T(n))+c(b_T(n-1))}{2n-3},\text{ and }\vspace*{1ex}\\ \mathcal{E}_S=-\frac{c(b_T(n))+c(b_T(n-1))}{2n-3}. \end{cases}\] Here, \(S\) is the upper standard Young tableau obtained from \(T\) by interchanging the positions of \(n\) and \(n-1\).
Recall \(Q\) from 3 . We now obtain \(\widehat{Q}(\lambda)\) for non-self-conjugate \(\lambda\vdash n\), and \(\widehat{Q}(\lambda^{\pm})\) for self-conjugate \(\lambda\vdash n\). The proof is straightforward application of Schur’s lemma [32], and it is well known in the literature (for instance, see [34]). However, we present the following lemma to make
this article self contained.
Lemma 4. Let \(n>4,\;\lambda\vdash n\), and \(\chi^{\lambda}\) denote the irreducible character of the symmetric group \(S_n\)
indexed by \(\lambda\). Then, we have the following: \[\begin{cases} \widehat{Q}(\lambda)=\frac{\chi^{\lambda}((1,2,3))}{d_{\lambda}}\;I_{d_{\lambda}}&\text{ if }\lambda\text{ is a
non-self-conjugate partition of }n,\vspace*{1ex}\\ \widehat{Q}(\lambda^+)=\widehat{Q}(\lambda^-)=\frac{\chi^{\lambda}((1,2,3))}{d_{\lambda}}\;I_{(1/2)d_{\lambda}}&\text{ if }\lambda\text{ is a self-conjugate partition of }n. \end{cases}\] Here,
\(I_k\) denotes the identity matrix of size \(k\times k\).
Proof. Let \(D\) be an irreducible \(A_n\)-module and ‘\(\mathop{\mathrm{Ch}}\)’ be the corresponding irreducible character. Then, \(\widehat{Q}(D)\) is the action of the group algebra element \(\frac{3}{n(n-1)(n-2)}Q_n\) on \(D\), where \[Q_n:=\sum_{\substack{\pi\text{ is a}\\3\text{-cycle}}}\pi=\sum_{1\leq i<j<k\leq n}\left((i,j,k)+(i,k,j)\right)\;\;\in\mathbb{C}[A_n].\] Let us observe that \(Q_n\) commutes with all the
elements of \(A_n\). Thus, Schur’s lemma [32] implies that \(Q_n\) acts on \(D\) like scalars. Therefore, we have \(\widehat{Q}(D)=C_D\;I_{\dim(D)}\) for some constant \(C_D\in\mathbb{C}\). Now, applying the \(\mathop{\mathrm{trace}}\) from both side we get that \[C_D=\frac{3}{n(n-1)(n-2)}\frac{\binom{n}{3}\left(\mathop{\mathrm{Ch}}(1,2,3)+\mathop{\mathrm{Ch}}(1,3,2)\right)}{\dim(D)}=\frac{\mathop{\mathrm{Ch}}(1,2,3)+\mathop{\mathrm{Ch}}(1,3,2)}{2\times\dim(D)}.\] Thus, we have that
\[\label{eq:eig46v46953-cyc95rw} \widehat{Q}(D)=\frac{\mathop{\mathrm{Ch}}(1,2,3)+\mathop{\mathrm{Ch}}(1,3,2)}{2\times\dim(D)}\;I_{\dim(D)}.\tag{16}\] We first
consider a non-self-conjugate partition \(\lambda\vdash n\). Recall the irreducible \(A_n\)-module \(D_{\lambda}\) and \(\dim(D_{\lambda})=d_{\lambda}\). Let \(\mathop{\mathrm{Ch}}^{\lambda}\) denote the irreducible character of \(A_n\) indexed by \(\lambda\). Then, using \(\mathop{\mathrm{Ch}}^{\lambda}=\chi^{\lambda}\)[33] and 16 we have that \[\widehat{Q}(\lambda)=\widehat{Q}(D_{\lambda})=\frac{\chi^{\lambda}((1,2,3))}{d_{\lambda}}\;I_{d_{\lambda}}.\]
We now focus on a self-conjugate partition \(\lambda\vdash n\). Recall the irreducible \(A_n\)-modules \(D_{\lambda}^{\pm}\) and \(\dim(D_{\lambda}^{\pm})=d_{\lambda}^{\pm}=\frac{1}{2}d_{\lambda}\), and denote their (respective) characters by \(\mathop{\mathrm{Ch}}_{\pm}^{\lambda}\). The cycle type for the \(3\)-cycle is \((3,1^{n-3})\vdash n\); moreover, \((3,1^{n-3})\) is not the partition formed by the hook-lengths of the diagonal boxes in \(\lambda\) and \(n>4\) (because \(\lambda\) is self-conjugate). Therefore, we have \(\mathop{\mathrm{Ch}}_{\pm}^{\lambda}(1,2,3)=\mathop{\mathrm{Ch}}_{\pm}^{\lambda}(1,3,2)=\frac{1}{2}\chi^{\lambda}((1,2,3))\)[33] and
hence 16 implies \[\widehat{Q}(\lambda^{\pm})=\widehat{Q}(D_{\lambda}^{\pm})=\frac{\chi^{\lambda}((1,2,3))}{d_{\lambda}}\;I_{d_{\lambda}}.\qedhere\] ◻
In this section, we prove 1. We use 2 and compare the transpose top-\(2\) with random shuffle with the random walks generated by all \(3\)-cycles. Before coming into the proof of 1,
we will prove some useful results. Given any partition \(\lambda\) of \(n\), throughout this section we denote the normalised character \(\frac{\chi^{\lambda}(1,2,3)}{d_{\lambda}}\) by \(\mathcal{C}_{\lambda}\), and the largest part of \(\lambda\) by \(\lambda_1\).
Lemma 5. Given any \(\varepsilon>0\) and \(c\in\mathbb{R}\), there exists \(M=M(c,\varepsilon)>0\) and sufficiently large \(N=N(c,\varepsilon,M)>M\) such that \[\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq
n-M}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log n+c)\rceil}-\mathcal{E}_T^{\lceil\left(n-\frac{3}{2}\right)(\log
n+c)\rceil}\right)^2<\frac{\varepsilon}{2},\] for all \(n\geq N\). Here, the notations have the same meaning as they are given in 3.
Proof. To prove the lemma, it is enough to show the existence of \(M=M(c,\varepsilon)>0\) and sufficiently large \(N=N(c,\varepsilon,M)>M\) such that
\[\label{eq:Error-term1} \sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq
n-M}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\frac{2n}{3}(\log n+c)}+\mathcal{E}_T^{\left(2n-3\right)(\log n+c)}\right)<\frac{\varepsilon}{4},\tag{17}\]
for all \(n\geq N\); because of the following:
Given any two real numbers \(a\) and \(b\), we have \((a-b)^2\leq 2(a^2+b^2)\),
\(x\leq\lceil x\rceil\) for any real number \(x\), and \(0\leq \mathcal{C}_{\lambda}^2,\mathcal{E}_T^2\leq 1\).
Let us choose a large enough positive integer \(M_1=M_1(c,\varepsilon)\) such that \[\label{eq:Error-term2} \sum_{m\geq
r}\frac{e^{-2mc}}{m!}\leq\frac{\varepsilon}{8}\text{ for all }r\geq M_1.\tag{18}\] For every \(\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\), we have \(c(b_T(n))+c(b_T(n-1))\leq 2\lambda_1-3\), i.e., by 3, \(\mathcal{E}_T^2\leq\left(\frac{2\lambda_1-3}{2n-3}\right)^2\) for all \(T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\). Now, for every \(r\in\{1,\dots,n-1\}\), \[\begin{align} &\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq
n-r}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\mathcal{E}_T^{2\left(n-\frac{3}{2}\right)(\log n+c)} \nonumber\\
\leq&\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq
n-r}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(1-\frac{2(n-\lambda_1)}{2n-3}\right)^{2\left(n-\frac{3}{2}\right)(\log n+c)}.\label{eq:Error-term3}
\end{align}\tag{19}\] Using \(1-x\leq e^{-x}\) for all \(x\geq 0\) and \(\displaystyle\sum_{\substack{\lambda\vdash n\;:\;\lambda_1\leq
n-r\\\lambda\notin\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}}}d_{\lambda}\displaystyle\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}e^{-2\left(n-\lambda_1\right)(\log n+c)}\geq 0,\) the expression
in the right hand side of 19 is less than or equal to \[\label{eq:Error-term4} \sum_{\lambda\vdash n\;:\;\lambda_1\leq
n-r}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}e^{-2\left(n-\lambda_1\right)(\log n+c)}.\tag{20}\] Recalling \(|\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}|=d_{\lambda}\text{ or }\frac{d_{\lambda}}{2}\) from 14 , the expression in 20 is less
than \[\begin{align} \displaystyle\sum_{\lambda\vdash n\;:\;\lambda_1\leq n-r}d_{\lambda}^2e^{-2\left(n-\lambda_1\right)(\log n+c)}\leq&\sum_{\lambda_1=1}^{n-r}\sum_{\substack{\xi\vdash
(n-\lambda_1)\\\xi_1\leq\lambda_1}}\binom{n}{\lambda_1}^2d_{\xi}^2e^{-2\left(n-\lambda_1\right)(\log n+c)}\tag{21}\\ \leq&\sum_{\lambda_1=1}^{n-r}\binom{n}{\lambda_1}^2e^{-2\left(n-\lambda_1\right)(\log n+c)}\sum_{\xi\vdash
(n-\lambda_1)}d_{\xi}^2.\tag{22}
\end{align}\] The inequality in 21 follows from the fact \(d_{\lambda}\leq\binom{n}{\lambda_1}d_{\xi}\) for all \(\xi\vdash (n-\lambda_1)\) with \(\xi_1\leq\lambda_1\). Since \(\displaystyle\sum_{\xi\, \vdash \,(n-\lambda_1)}d_{\xi}^2=(n-\lambda_1)!\), writing \(m\) for \(n-\lambda_1\), the expression in the right hand side of 22 is equal to \[\label{eq:Error-term7} \sum_{m=r}^{n-1}\binom{n}{m}^2e^{-2m(\log n+c)}m!\leq \sum_{m=r}^{n-1}\frac{n^{2m}}{m!}e^{-2m(\log
n+c)}=\sum_{m=r}^{n-1}\frac{e^{-2mc}}{m!}<\sum_{m\geq r}\frac{e^{-2mc}}{m!}.\tag{23}\] The leftmost inequality in 23 follows from \(\binom{n}{m}\leq\frac{n^m}{m!}\). Thus,
the expression in 20 , and hence the expression in the right hand side of 19 is less than \(\displaystyle\sum_{m\geq r}\frac{e^{-2mc}}{m!}\). Therefore,
using 18 , we have the following: \[\label{eq:Error-term-key-I}
\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq n-r}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\mathcal{E}_T^{2\left(n-\frac{3}{2}\right)(\log
n+c)}<\frac{\varepsilon}{8}\text{ for all }r\geq M_1.\tag{24}\]
On the other hand, [18] ensures the existence of \(M=M(c,\varepsilon)\geq M_1\) and sufficiently large \(N=N(c,\varepsilon,M)>M\) such that \[\label{eq:Error-term8} \sum_{\lambda\vdash n\;:\;\lambda_1\leq
n-M}d_{\lambda}\left|\mathcal{C}_{\lambda}\right|^{\frac{n}{3}(\log n+c)}<\frac{\sqrt{\varepsilon}}{2\sqrt{2}}\quad\quad\text{ for all }n\geq N,\tag{25}\] thanks to Nestoridi and Olesker-Taylor for the delicate proof. Now,
\[\begin{align} \sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq
n-M}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\mathcal{C}_{\lambda}^{\frac{2n}{3}(\log n+c)}<&\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq
n-M}}d_{\lambda}^2\mathcal{C}_{\lambda}^{\frac{2n}{3}(\log n+c)} \tag{26}\\ \leq&\sum_{\lambda\vdash n\;:\;\lambda_1\leq n-M}d_{\lambda}^2\mathcal{C}_{\lambda}^{\frac{2n}{3}(\log n+c)} \tag{27}\\ \leq&\left(\sum_{\substack{\lambda\vdash
n\\\lambda_1\leq n-M}}d_{\lambda}\left|\mathcal{C}_{\lambda}\right|^{\frac{n}{3}(\log n+c)}\right)^2.\tag{28}
\end{align}\] The inequality in 26 follows
from the fact that \(|\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}|=d_{\lambda}\) or \(\frac{d_{\lambda}}{2}\). The inequality in 27 holds because \(\displaystyle\sum_{\substack{\lambda\vdash n\;:\;\lambda_1\leq
n-M\\\lambda\notin\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}}}d_{\lambda}^2\mathcal{C}_{\lambda}^{\frac{2n}{3}(\log n+c)}\geq 0.\) Therefore, 25 and the expression in 28 implies that \[\label{eq:Error-term-key-II} \sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq
n-M}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\mathcal{C}_{\lambda}^{\frac{2n}{3}(\log n+c)}<\frac{\varepsilon}{8}\quad\quad\text{ for all }n\geq N.\tag{29}\] Finally, 17 follows from 24 and 29 , by setting \(r=M\geq M_1\). The proof finishes here. ◻
Remark 3. We emphasize that the constant \(M\) in 5 is sufficiently large and depends on \(c\) and \(\varepsilon\), but not on \(n\). The same applies to the upcoming 6, 11, and 12.
Let \(\lambda\) be a Young diagram with \(n\) boxes (i.e., \(\lambda\vdash n\)). An inner corner of \(\lambda\)
is a box whose removal from \(\lambda\) results in a valid Young diagram with \(n-1\) boxes. We write \(\lambda^{\downarrow}\) to denote the set of all Young
diagrams obtained by removing an inner corner from \(\lambda\). Then, application of the hook-length formula provides \[\label{eq:dimension-ineq} d_{\zeta}\leq\frac{4^{n-\lambda_1}}{n}d_{\lambda},\;\text{ for all }\zeta\in\lambda^{\downarrow}\text{ satisfying }\zeta_1=\lambda_1\;\; \text{(see \cite{N-star_limit})}.\tag{30}\]
Lemma 6. Given any \(\varepsilon>0\) and \(c\in\mathbb{R}\), recall \(M\) from 5. Then, \[\lim_{n\rightarrow\infty}\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq
\lambda_1<n}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log n+c)\rceil}-\mathcal{E}_T^{\lceil\left(n-\frac{3}{2}\right)(\log
n+c)\rceil}\right)^2=0.\] The notations have the same meaning as they are given in 3 and 4.
Proof. For \(\lambda\vdash n\), we partition the set \(\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\) into two subsets as follows: \[\begin{align} \mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)&=\{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}:\text{ both }n-1\text{ and }n\text{ are in the first row of }T\}.\\
\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)&=\{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}:\;n-1\text{ or }n\text{ is below the first row of }T\} \\
&=\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\setminus\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda).
\end{align}\] Throughout this proof, we use \(\mathcal{C}_{\lambda}=e^{-\frac{3}{n}(n-\lambda_1)}\left(1+O\left(\frac{3}{n^2}\right)\right)\) for all \(\lambda\vdash n\) satisfying
\(n-\lambda_1\ll n\), from [18]. Thus, for sufficiently large \(n\), using \(1+O\left(\frac{3}{n^2}\right)\approx e^{O(3/n^2)}\), we have that \[\label{eq:Main-term1} \mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log
n+c)\rceil}=e^{o(1)-(n-\lambda_1)(\log n+c)},\tag{31}\] for all \(\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\) satisfying \(n-M\leq\lambda_1<n\). Now,
\[\begin{align} \mathcal{S}_1(n):=&\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq
\lambda_1<n}}d_{\lambda}\sum_{T\in\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log n+c)\rceil}-\mathcal{E}_T^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2 \nonumber\\
=&\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq \lambda_1<n}}d_{\lambda}\sum_{T\in\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)}\left(e^{o(1)-(n-\lambda_1)(\log
n+c)}-\left(\frac{2\lambda_1-3}{2n-3}\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2.\label{eq:Main-term2}
\end{align}\tag{32}\] The equality in 32 follows from 31 and 3. Also, using \[\begin{array}{lr} |\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)|\leq\begin{cases} d_{\lambda}&\text{ for non-self-conjugate }\lambda,\\
\frac{d_{\lambda}}{2}&\text{ for self-conjugate }\lambda, \end{cases}&\text{ and }\;\left(\frac{2\lambda_1-3}{2n-3}\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\approx e^{-(n-\lambda_1)(\log n+c)}, \end{array}\] the expression
in the right hand side of 32 , i.e., \(\mathcal{S}_1(n)\) is less than \[\displaystyle\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq \lambda_1<n}}d_{\lambda}^2e^{-2(n-\lambda_1)(\log n+c)}\left(e^{o(1)}-1\right)^2.\] Therefore, \(\displaystyle\sum_{\substack{\lambda\vdash n\;:\;n-M\leq \lambda_1<n\\\lambda\notin\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}}}d_{\lambda}^2e^{-2(n-\lambda_1)(\log n+c)}\left(e^{o(1)}-1\right)^2\geq 0\) implies
that \[\begin{align} \mathcal{S}_1(n)<&\sum_{\lambda\vdash n\;:\;n-M\leq \lambda_1<n}d_{\lambda}^2e^{-2(n-\lambda_1)(\log n+c)}\left(e^{o(1)}-1\right)^2 \nonumber\\
\leq&\sum_{\lambda_1=n-M}^{n-1}\binom{n}{\lambda_1}^2(n-\lambda_1)!\;e^{-2(n-\lambda_1)(\log n+c)}\left(e^{o(1)}-1\right)^2 \tag{33}\\ \leq&\sum_{m=1}^{M}\frac{n^{2m}}{m!}\;e^{-2m(\log n+c)}\left(e^{o(1)}-1\right)^2,\;\text{ setting
}m=n-\lambda_1\text{ and using } \binom{n}{m}\leq\frac{n^m}{m!} \nonumber\\
=&\sum_{m=1}^{M}\frac{\left(e^{-2c}\right)^m}{m!}\left(e^{o(1)}-1\right)^2<\sum_{m=1}^{\infty}\frac{\left(e^{-2c}\right)^m}{m!}\left(e^{o(1)}-1\right)^2=\left(e^{e^{-2c}}-1\right)\left(e^{o(1)}-1\right)^2\tag{34}.
\end{align}\] The inequality in 33 follows from the facts that \(d_{\lambda}\leq\binom{n}{\lambda_1}d_{\xi}\) for all \(\xi \vdash (n-\lambda_1)\) with \(\xi_1\leq\lambda_1\) and \(\displaystyle\sum_{\xi \, \vdash \,(n-\lambda_1)}d_{\xi}^2=(n-\lambda_1)!\). The expression in the right hand side of 34 approaches to zero as \(n\rightarrow\infty\). Therefore, using the non negativity of \(\mathcal{S}_1(n)\) we have that \[\label{eq:Main-term-key-I} \lim_{n\rightarrow\infty}\mathcal{S}_1(n)=0.\tag{35}\] Again, using the triangle inequality of real numbers and 31 , we have that
\[\begin{align} \mathcal{S}_2(n):=&\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq
\lambda_1<n}}d_{\lambda}\sum_{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log n+c)\rceil}-\mathcal{E}_T^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2 \nonumber\\
\leq&\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq \lambda_1<n}}d_{\lambda}\sum_{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)}\left(e^{o(1)-(n-\lambda_1)(\log
n+c)}+\left|\mathcal{E}_T\right|^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2 \nonumber\\ \leq&\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq
\lambda_1<n}}d_{\lambda}\sum_{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)}\left(e^{o(1)-(n-\lambda_1)(\log n+c)}+\left|\frac{2\lambda_1-3}{2n-3}\right|^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2.\label{eq:Main-term5}
\end{align}\tag{36}\] The inequality in 36 follows from 3 and \[c(b_T(n))+c(b_T(n-1))\leq 2\lambda_1-3,\;\text{ i.e., }\left|\mathcal{E}_T\right|\leq\left|\frac{2\lambda_1-3}{2n-3}\right|,\] for all \(\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\). As \(n\) is sufficiently large throughout this proof, we have that \[\left|\frac{2\lambda_1-3}{2n-3}\right|^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}=\left|1-\frac{n-\lambda_1}{n-\frac{3}{2}}\right|^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\approx\;e^{-(n-\lambda_1)(\log
n+c)}.\] For every \(T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda),\;\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\) satisfying \(n-M\leq\lambda_1<n\), at
least one of \(n-1\) or \(n\) sits at an inner corner of \(\lambda\) below the first row. Also, there could be at most \(M\)
many inner corner below the first row of \(\lambda\). Therefore, using 30 , we have that \[|\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)|\leq\begin{cases}
\frac{M\times4^{n-\lambda_1}}{n}d_{\lambda}\leq \frac{M\times4^{M}}{n}d_{\lambda}&\text{ for non-self-conjugate }\lambda,\\ \frac{M\times4^{n-\lambda_1}}{n}\frac{d_{\lambda}}{2}\leq \frac{M\times4^{M}}{n}\frac{d_{\lambda}}{2}&\text{ for
self-conjugate }\lambda. \end{cases}\] Thus, the right hand side of 36 , and hence \(\mathcal{S}_2(n)\) is less than or equal to \[\begin{align} &\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq \lambda_1<n}}\frac{M\times4^{M}}{n}\;d_{\lambda}^2\;e^{-2(n-\lambda_1)(\log n+c)}\left(e^{o(1)}+1\right)^2 \nonumber\\
\leq&\sum_{\lambda\vdash n\;:\;n-M\leq \lambda_1<n}\frac{M\times4^{M}}{n}\;d_{\lambda}^2\;e^{-2(n-\lambda_1)(\log n+c)}\left(e^{o(1)}+1\right)^2 \tag{37}\\
\leq&\sum_{\lambda_1=n-M}^{n-1}\frac{M\times4^{M}}{n}\;\binom{n}{\lambda_1}^2\;(n-\lambda_1)!\;e^{-2(n-\lambda_1)(\log n+c)}\left(e^{o(1)}+1\right)^2 \tag{38}\\ =&\frac{M\times4^{M}}{n}\sum_{m=1}^{M}\frac{\prod_{i=0}^{m-1}(n-i)^2}{m!}\;e^{-2m(\log
n+c)}\left(e^{o(1)}+1\right)^2,\;\;\text{ writing }m\text{ for }n-\lambda_1 \nonumber\\ \leq&\frac{M\times4^{M}}{n}\sum_{m=1}^{M}\frac{n^{2m}}{m!}\;e^{-2m(\log n+c)}\left(e^{o(1)}+1\right)^2 \nonumber
\end{align}\]\[=\frac{M\times4^{M}}{n}\sum_{m=1}^{M}\frac{\left(e^{-2c}\right)^m}{m!}\left(e^{o(1)}+1\right)^2<\frac{M\times4^{M}}{n}\left(e^{e^{-2c}}-1\right)\left(e^{o(1)}+1\right)^2.\] The inequality in 37 follows from the fact that \[\sum_{\substack{\lambda\vdash n\;:\;n-M\leq
\lambda_1<n\\\lambda\notin\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}}}\frac{M\times4^{M}}{n}\;d_{\lambda}^2\;e^{-2(n-\lambda_1)(\log n+c)}\left(e^{o(1)}+1\right)^2\geq 0.\] The inequality in 38 follows
from the facts that \(d_{\lambda}\leq\binom{n}{\lambda_1}d_{\xi}\) for all \(\xi\vdash (n-\lambda_1)\) with \(\xi_1\leq\lambda_1\) and \(\displaystyle\sum_{\xi\vdash (n-\lambda_1)}d_{\xi}^2=(n-\lambda_1)!\). Thus, \[0\leq \mathcal{S}_2(n)\leq\frac{M\times4^{M}}{n}\left(e^{e^{-2c}}-1\right)\left(e^{o(1)}+1\right)^2,\] for all
sufficiently large \(n\), i.e., \[\label{eq:Main-term-key-II}
\lim_{n\rightarrow\infty}\mathcal{S}_2(n)=0.\tag{39}\] Therefore, the lemma follows from 35 , 39 , and the following: \[\begin{align}
0&\leq \sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq
\lambda_1<n}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log n+c)\rceil}-\mathcal{E}_T^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2\\
&\leq\mathcal{S}_1(n)+\mathcal{S}_2(n),\;\text{ for all sufficiently large }n.\qedhere
\end{align}\] ◻
Following the notations of 6, we note down an immediate corollary as follows:
Corollary 7. There exists large enough positive integer \(\bar{N}=\bar{N}(c,\varepsilon,M)>0\) such that, \[\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M<
\lambda_1<n}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log n+c)\rceil}-\mathcal{E}_T^{\lceil\left(n-\frac{3}{2}\right)(\log
n+c)\rceil}\right)^2<\frac{\varepsilon}{2},\text{ for all }n\geq \bar{N}.\]
Proof of 1. Nestoridi and Olesker-Taylor [18]
obtained the limit profile for the random walk on \(A_n\) generated by all \(3\)-cycles. Their result shows \[\lim_{n\rightarrow\infty}\left\|Q^{*\lceil\frac{n}{3}\log n+cn\rceil}-U_{A_n}\right\|_{\text{TV}}=d_{\text{TV}}\left(\text{Poi}(1+e^{-c}),\text{Poi}(1)\right),\;c\in\mathbb{R}.\] Therefore, the theorem follows from 2 and \(\displaystyle\lim_{n\rightarrow\infty}\sum_{\rho\in\widehat{A_n}}\mathop{\mathrm{\mathbf{Term}}}_{\rho}=0\); where
\[\label{eq:key} \mathop{\mathrm{\mathbf{Term}}}_{\rho}:= d_{\rho} \mathop{\mathrm{trace}}\left(\left(\widehat{Q}(\rho)\right)^{\lceil\frac{n}{3}(\log
n+c)\rceil}-\left(\widehat{P}(\rho)\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2\text{ for }\rho\in\widehat{A_n}.\tag{40}\] Recall the irreducible representations of \(A_n\) from 15 . They are given by \[\widehat{A_n}=\big\{D_{\lambda}:\lambda\in\mathop{\mathrm{NCPar(n)}}\big\}\bigcup\big\{D^+_{\lambda},D^-_{\lambda}:\lambda\in\mathop{\mathrm{CPar(n)}}\big\}.\] We
now focus on each summand, given in 40 , indexed by the irreducible representations on \(A_n\). For \(\lambda\in\mathop{\mathrm{NCPar(n)}}\), there is an irreducible
representation of \(A_n\), and \[\begin{align}
\label{eq:key1} \mathop{\mathrm{\mathbf{Term}}}_{\lambda}=&d_{\lambda}\mathop{\mathrm{trace}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log n+c)\rceil}I_{d_{\lambda}}-\left(\widehat{P}(\lambda)\right)^{\lceil\left(n-\frac{3}{2}\right)(\log
n+c)\rceil}\right)^2 \nonumber\\ =&d_\lambda\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log
n+c)\rceil}-\left(\mathcal{E}_T\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2,
\end{align}\tag{41}\] by 4 and 3. Also, for \(\lambda\in\mathop{\mathrm{CPar(n)}}\), there are two irreducible representations \(\lambda^{\pm}\) of \(A_n\), and \[\begin{align} \mathop{\mathrm{\mathbf{Term}}}_{\lambda^{\pm}}=&\frac{d_{\lambda}}{2}\mathop{\mathrm{trace}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log
n+c)\rceil}I_{d_{\lambda/2}}-\left(\widehat{P}(\lambda^{\pm})\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2 \nonumber\\
=&\frac{d_{\lambda}}{2}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log n+c)\rceil}-\left(\mathcal{E}_T\right)^{\lceil\left(n-\frac{3}{2}\right)(\log
n+c)\rceil}\right)^2.
\end{align}\] by 4 and 3. Therefore, we have that \[\begin{align}
\label{eq:key2} &\sum_{\rho\in\{\lambda^+,\lambda^-\}}\mathop{\mathrm{\mathbf{Term}}}_{\rho} =&d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log
n+c)\rceil}-\left(\mathcal{E}_T\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2.
\end{align}\tag{42}\] for \(\lambda\in\mathop{\mathrm{CPar(n)}}\). Thus, combining 41 and 42 we have that \[\begin{align}
0\leq&\sum_{\rho\in\widehat{A_n}}\mathop{\mathrm{\mathbf{Term}}}_{\rho}
\leq\sum_{\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}}d_{\lambda}\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\mathcal{C}_{\lambda}^{\lceil\frac{n}{3}(\log
n+c)\rceil}-\left(\mathcal{E}_T\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\right)^2.\nonumber
\end{align}\] The summand corresponding to \(\lambda=(n)\) is zero. Thus, 5 and 7 together imply \(0\leq\displaystyle\sum_{\rho\in\widehat{A_n}}\mathop{\mathrm{\mathbf{Term}}}_{\rho}<\varepsilon\) for all \(n\geq\max\{N,\bar{N}\}\). This completes the proof. ◻
We conclude this section with the following question for further exploration:
Open Question 1. Determine if the following random walk models exhibit the cutoff phenomenon and, if so, derive their limiting profiles:
The random walk generated by star \(k\)-cycles for \(k=o(n)\), specifically the walks generated by \((1,2,\dots,k-1,i)\) and \((i,k-1,k-2,\dots,2)\) for \(k\leq i\leq n\) and \(k=o(n)\).
The random walk generated by star conjugacy classes, for example,
The random walk generated by \((1,2,3)(4,i)\) and \((4,i)(3,2,1)\) for \(5\leq i\leq n\), or
The random walk generated by \((1,2,i)(4,5)\) and \((4,5)(i,2,1)\) for \(i=3,\;6\leq i\leq n\).
Huang and Huang obtained the second-largest eigenvalues of the alternating group graph, extended alternating group graph, complete alternating group graph and asked the questions on the complete spectrum of them. The answer below for the
alternating group graph follows directly from 3. The notations in this section have the same meaning as they are in 3.
Recall that the alternating group graph \(AG_n\) is the Cayley graph on \(A_n\) with generating set \(\{(1,i,2),(1,2,i):3\leq i\leq n\}\). Therefore, the
adjacency matrix of \(AG_n\) is given by the (right) multiplication action of the group algebra element \[\displaystyle\sum_{i=3}^{n}\left((1,2,i)+(1,i,2)\right)\in\mathbb{C}[A_n]\] on the
group algebra \(\mathbb{C}[A_n]\). But, the equality \[\begin{align} \sum_{i=3}^{n}\left((1,2,i)+(1,i,2)\right)
=&(1,n)(2,n-1)\left(\sum_{i=1}^{n-2}\left((n-1,n,i)+(n,n-1,i)\right)\right)(1,n)(2,n-1)
\end{align}\] implies that the adjacency matrix of \(AG_n\) is similar to \((2n-3)\widehat{P}(R)-I_{\frac{n!}{2}}\). Here, \(R\) is the right regular
representation of the alternating group and \(I_{\frac{n!}{2}}\) denote the identity matrix of size \(\frac{n!}{2}\times\frac{n!}{2}\). Therefore, the full spectrum is immediate from 3, and it is formally given below:
Theorem 8. For \(\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\), the eigenvalues of the adjacency matrix of \(AG_n\) are indexed by the set \(\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\). For non-self-conjugate \(\lambda\vdash n\), each eigenvalue repeats \(d_{\lambda}\) many times. For self-conjugate \(\lambda\vdash n\), each eigenvalue repeats \(\frac{d_{\lambda}}{2}\) many times. Suppose \(\mathcal{E'}_T\) denote the eigenvalue indexed by \(T\in \mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\).
If \(n-1\) and \(n\) appear in the same row of \(T\), then \(\mathcal{E'}_T=c(b_T(n))+c(b_T(n-1))-1\).
If \(n-1\) and \(n\) appear in the same column of \(T\), then \(\mathcal{E'}_T=-c(b_T(n))-c(b_T(n-1))-1\).
If \(n-1\) and \(n\) appear neither in the same row nor in the same row of \(T\), then \[\begin{cases}
\mathcal{E'}_T=c(b_T(n))+c(b_T(n-1))-1 \text{ and }\vspace*{1ex}\\ \mathcal{E'}_S=-c(b_T(n))-c(b_T(n-1))-1. \end{cases}\] Here, \(S\) is the upper standard Young tableau obtained from \(T\) by interchanging the positions of \(n\) and \(n-1\).
6 Example when the transition matrices do not commute↩︎
We consider the random walk on \(A_n\) driven by the following probability measure: \[\label{eq:TT39R95defn} P'(\pi)= \begin{cases}
\frac{1}{(n-1)^2}&\text{ if }\pi=(i,j,n)\text{ or }(j,i,n)\text{ for }1\leq i<j\leq n-1,\\ \frac{1}{n-1}&\text{ if }\pi=\mathop{\mathrm{id}},\text{ the identity permutation},\\ 0&\text{ otherwise}. \end{cases}\tag{43}\] The
transition matrix of this random walk on \(A_n\) is the action of \(\frac{1}{(n-1)^2}P'_n\in\mathbb{C}[A_n]\), where \[P'_n=(n-1)\mathop{\mathrm{id}}+\sum_{1\leq i<j\leq n-1}\left((i,j,n)+(j,i,n)\right),\] on \(A_n\) by multiplication on the right. Also, the transition matrix of the transpose top-\(2\) with random shuffle is the action of \(\frac{1}{2n-3}P_n\in\mathbb{C}[A_n]\), where \[P_n=\mathop{\mathrm{id}}+\sum_{1\leq i\leq
n-2}\left((i,n-1,n)+(i,n,n-1)\right),\] on \(A_n\) by multiplication on the right. It can be checked that \(P_nP'_n\neq P'_nP_n\) for all \(n\geq
4\). Therefore, the transition matrices \(\widehat{P}(R)\) and \(\widehat{P'}(R)\) are not simultaneously diagonalizable; where \(R\) is the right
regular representation of \(A_n\). As a result, Nestoridi’s comparison technique [27] fails to compare the random
walks on \(A_n\) driven by the probability measures \(P\) and \(P'\). However, we can apply our comparison method (given in 2) to compare these two random walks. This is because, for each irreducible representation \(\rho\) of \(A_n\), the
matrices \(\widehat{P}(\rho)\) and \(\widehat{P'}(\rho)\) are simultaneously block-diagonalizable with block size at most \(2\).
We now write down the relation between \(P_n\) and \(P'_n\) with the Young-Jucys-Murphy (YJM) elements of \(A_n\)[1], [35]. The \(i\)th YJM element \(J_i\) of \(A_n\) is given by \[J_i:=(1,2)\left((1,i)+(2,i)+\cdots+(i-1,i)\right),\quad i\geq 3,\] with \(J_1=0\) and \(J_2=\mathop{\mathrm{id}}\)[1]. It can be verified that \(P_n'=J_n^2\) for all \(n\geq 3\). Additionally, recall that \[P_n=(1,2)(n-1,n)\left(J_{n-1}+J_n\right),\] holds for \(n>3\)[1]. We also recall the set of all (non-isomorphic) irreducible \(A_n\)-modules: \[\big\{D_{\lambda}:\lambda\in\mathop{\mathrm{NCPar(n)}}\big\}\bigcup\big\{D^+_{\lambda},D^-_{\lambda}:\lambda\in\mathop{\mathrm{CPar(n)}}\big\},\] from 15 . We work with the basis used in
the proof of 3 by the first author (for details, see [1]). For \(\lambda\in\mathop{\mathrm{NCPar(n)}}\) (respectively, \(\lambda\in\mathop{\mathrm{CPar(n)}}\)) and \(T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\), let \(v_T\) (respectively, \(v_T^{\pm}\)) be the basis vector of \(D_{\lambda}\) (respectively, \(D_{\lambda}^{\pm}\)) indexed by \(T\), and determined by \(J_i(v_T)=c(b_T(i))v_T\) (respectively,
\(J_i(v_T^{\pm})=c(b_T(i))v_T^{\pm}\)) for \(1\leq i\leq n\).
For \(\lambda\in\mathop{\mathrm{NCPar(n)}}\), we partition the basis into three subsets, as follows: \[\begin{align} &\mathcal{B}_1:=\{v_T: c(b_T(n))=c(b_T(n-1))+1\},\;\mathcal{B}_2:=\{v_T:
c(b_T(n))=c(b_T(n-1))-1\},\text{ and }\\ &\mathcal{B}_3:=\{v_T,(1,2)(n-1,n)v_{T}: c(b_T(n))\neq c(b_T(n-1))\pm 1\text{ and }c(b_T(n-1))<c(b_T(n))\}.
\end{align}\] From [1], we recall that \[(1,2)(n-1,n)\cdot v_T=\begin{cases} v_T&\text{ if }v_T\in\mathcal{B}_1,\\
-v_T&\text{ if }v_T\in\mathcal{B}_2. \end{cases}\] Therefore, the vectors in \(\mathcal{B}_1\) and \(\mathcal{B}_2\) are common eigenvectors of both \(P_n\) and \(P_n'\), with the following eigenvalue relations: \[\begin{align} &P_n(v_T)=(2c(b_T(n))-1)v_T\text{ and
}P_n'(v_T)=\left(c(b_T(n))\right)^2v_T,\text{ if }v_T\in\mathcal{B}_1,\tag{44}\\ &P_n(v_T)=-(2c(b_T(n))+1)v_T\text{ and }P_n'(v_T)=\left(c(b_T(n))\right)^2v_T,\text{ if }v_T\in\mathcal{B}_2\tag{45}.
\end{align}\] For \(T\) such that \(c(b_T(n))\neq c(b_T(n-1))\pm 1\)
and \(c(b_T(n-1))<c(b_T(n))\), we have that \[\text{Span}\{\{v_T,v_{(n-1,n)T}\}\}=\text{Span}\{\{v_T,(1,2)(n-1,n)v_T\}\}\;\text{(by \cite{TT2R}).}\] Thus, \(\mathcal{B}_3\) has even cardinality, and can be partitioned into subsets of size two, such that the span of each subset is invariant under the action of both \(P_n\) and \(P_n'\). More specifically, for \(n>3\), we have the following: \[\begin{align} [P_n]_{\{v_T,(1,2)(n-1,n)v_T\}}=&\begin{pmatrix}
0&c(b_T(n-1))+c(b_T(n))\\&\\ c(b_T(n-1))+c(b_T(n))&0
\end{pmatrix} \text{ and }\tag{46}\\&\nonumber\\
[P_n']_{\{v_T,(1,2)(n-1,n)v_T\}}=&\begin{pmatrix} \left(c(b_T(n))\right)^2&c(b_T(n))+c(b_T(n-1))\\&\\ 0&\left(c(b_T(n-1))\right)^2
\end{pmatrix}.\tag{47}
\end{align}\]
For \(\lambda\in\mathop{\mathrm{CPar(n)}}\), by replacing \(D_{\lambda},v_T\), and \(\mathcal{B}_i (i=1,2,3)\) with \(D^{\pm}_{\lambda},v^{\pm}_T\), and \(\mathcal{B}^{\pm}_i (i=1,2,3)\), and using a simiar argument as above, we obtain \[\begin{align}
&P_n(v^{\pm}_T)=(2c(b_T(n))-1)v^{\pm}_T\text{ and }P_n'(v^{\pm}_T)=\left(c(b_T(n))\right)^2v^{\pm}_T,\text{ if }v^{\pm}_T\in\mathcal{B}^{\pm}_1,\tag{48}\\ &P_n(v^{\pm}_T)=-(2c(b_T(n))+1)v^{\pm}_T\text{ and
}P_n'(v^{\pm}_T)=\left(c(b_T(n))\right)^2v^{\pm}_T,\text{ if }v^{\pm}_T\in\mathcal{B}^{\pm}_2\tag{49}.
\end{align}\] Also, for \(T\) such that \(c(b_T(n))\neq
c(b_T(n-1))\pm 1\) and \(c(b_T(n-1))<c(b_T(n))\), we have that \[\begin{align} [P_n]_{\{v^{\pm}_T,(1,2)(n-1,n)v^{\pm}_T\}}=&\begin{pmatrix}
0&c(b_T(n-1))+c(b_T(n))\\&\\ c(b_T(n-1))+c(b_T(n))&0
\end{pmatrix} \text{ and }\tag{50}\\&\nonumber\\
[P_n']_{\{v^{\pm}_T,(1,2)(n-1,n)v^{\pm}_T\}}=&\begin{pmatrix} \left(c(b_T(n))\right)^2&c(b_T(n))+c(b_T(n-1))\\&\\ 0&\left(c(b_T(n-1))\right)^2
\end{pmatrix}.\tag{51}
\end{align}\]
We first prove the following lemma before comparing the two random walk models on \(A_n\) driven by \(P\) and \(P'\).
Lemma 9. For \(a,b,a',b',\kappa\geq 0\), and positive integers \(N_1\) and \(N_2\), we have the following: \[\label{eq:2x2matrix0} \mathop{\mathrm{trace}}\left(\begin{pmatrix} 0&a'+b'\\&\\ a'+b'&0 \end{pmatrix}^{N_1}-\begin{pmatrix} a^2&\frac{1}{\kappa}(a+b)\\&\\ 0&b^2
\end{pmatrix}^{N_2}\right)^2\leq a^{4N_2}+b^{4N_2}+2(a'+b')^{2N_1}.\qquad{(3)}\]
Proof. The straightforward application of the principle of mathematical induction on \(N_1\) and \(N_2\) implies the following: \[\begin{align} \begin{pmatrix} 0&a'+b'\\&\\ a'+b'&0 \end{pmatrix}^{N_1} &= (a'+b')^{N_1}\begin{pmatrix} \frac{1+(-1)^{N_1}}{2}&\frac{1-(-1)^{N_1}}{2}\\&\\
\frac{1-(-1)^{N_1}}{2}&\frac{1+(-1)^{N_1}}{2}
\end{pmatrix}\tag{52}\\&\nonumber\\ \begin{pmatrix} a^2&\frac{1}{\kappa}(a+b)\\&\\ 0&b^2 \end{pmatrix}^{N_2}&=\begin{pmatrix} a^{2N_2}&\frac{b^{2N_2}-a^{2N_2}}{\kappa(b-a)}\\&\\ 0&b^{2N_2} \end{pmatrix}.\tag{53}
\end{align}\] Therefore, for even \(N_1\), the fact that the trace of the square of a matrix equals the
sum of the squares of its eigenvalues implies that the expression in the left hand side of ?? is equal to \(\left((a'+b')^{N_1}-a^{2N_2}\right)^2+\left((a'+b')^{N_1}-b^{2N_2}\right)^2\). Thus, the lemma
follows from \[\left((a'+b')^{N_1}-a^{2N_2}\right)^2+\left((a'+b')^{N_1}-b^{2N_2}\right)^2\leq a^{4N_2}+b^{4N_2}+2(a'+b')^{2N_1}.\] For odd \(N_1\), the lemma
follows from the following \[\begin{align} &\mathop{\mathrm{trace}}\left(\begin{pmatrix} 0&a'+b'\\&\\ a'+b'&0 \end{pmatrix}^{N_1}-\begin{pmatrix} a^2&\frac{1}{\kappa}(a+b)\\&\\ 0&b^2
\end{pmatrix}^{N_2}\right)^2\\&\\ =&\mathop{\mathrm{trace}}\begin{pmatrix} a^{4N_2}+(a'+b')^{2N_1}-(a'+b')^{N_1}\cdot\frac{b^{2N_2}-a^{2N_2}}{\kappa(b-a)}&\clubsuit\\&\\
\spadesuit&b^{4N_2}+(a'+b')^{2N_1}-(a'+b')^{N_1}\cdot\frac{b^{2N_2}-a^{2N_2}}{\kappa(b-a)} \end{pmatrix}\\&\\
=&a^{4N_2}+b^{4N_2}+2(a'+b')^{2N_1}-2(a'+b')^{N_1}\frac{b^{2N_2}-a^{2N_2}}{\kappa(b-a)}\leq\;a^{4N_2}+b^{4N_2}+2(a'+b')^{2N_1}.\qedhere
\end{align}\] ◻
We now make a guess for the candidate cutoff time and cutoff window for the random walk on \(A_n\) driven by \(P'\). To do so, we focus on the irreducible representation of \(A_n\) indexed by \((n-1,1)\) (or equivalently \((2,1^{n-1})\))), and obtain the eigenvalues of \(\widehat{P'}(D_{(n-1,1)})\). Let us denote the elements of \(\text{UStd}((n-1,1))\cup\text{UStd}((2,1^{n-1}))\) as follows: \[T_2:=\begin{array}{c}\young({{\substack{1}}}{{\substack{2}}},{{\substack{3}}},{{\substack{\vdots}}},{{\substack{n}}})\end{array},
\quad T_n:=\begin{array}{c}\young({{\substack{1}}}{{\substack{2}}}{{\substack{\cdots}}}{{\tiny{\substack{n-1}}}},{{\substack{n}}})\end{array},\text{ and }
T_i:=\begin{array}{c}\young({{\substack{1}}}{{\substack{2}}}{{\substack{\cdots}}}{{\substack{n}}},{{\substack{i}}})\end{array}\text{ for }2<i<n.\] Now, consider the basis partition \(\{v_{T_i}:2<i<n-1\},\{v_{T_2}\},\{v_{T_{n-1}},(1,2)(n-1,n)v_{T_{n-1}}\}\). Using equations 44 , 45 , and 47 , we can
deduce the eigenvalues of \(\widehat{P'}(D_{(n-1,1)})\). These eigenvalues are given by:
\(\left(\frac{n-2}{n-1}\right)^2\), with multiplicity \(n-2\), and
\(\left(\frac{1}{n-1}\right)^2\), with multiplicity \(1\).
Therefore, we have that \[(n-2)\left(\frac{n-2}{n-1}\right)^{2k}+\left(\frac{1}{n-1}\right)^{2k}=(n-2)\left(1-\frac{1}{n-1}\right)^{2k}+\left(\frac{1}{n-1}\right)^{2k}\approx e^{-c},\] for \(k=\frac{1}{2}(n-1)(\log n+c)\). This indicates that \(\frac{1}{2}(n-1)\log n\) would be a possible candidate for the cutoff time, with a window of order \(n\).
We now use 2 to compare the random walks on \(A_n\) driven by \(P\) and \(P'\). To begin, let us introduce some notation that we will use throughout the rest of this section. We denote \[\label{eq:P-P39-component}
\mathop{\mathrm{\mathbf{Tally}}}_{\rho}:=\mathop{\mathrm{trace}}\left(\left(\widehat{P}(\rho)\right)^{\left\lceil\left(n-\frac{3}{2}\right)(\log n+c)\right\rceil}-\left(\widehat{P'}(\rho)\right)^{\left\lceil\frac{1}{2}(n-1)(\log
n+c)\right\rceil}\right)^2,\text{ for }\rho\in\widehat{A_n}.\tag{54}\] In particular, when \(\rho=D_{\lambda},\;\lambda\in\mathop{\mathrm{NCPar(n)}}\), we simply write \(\lambda\) in place of \(D_{\lambda}\). Similarly, when \(\rho=D^{\pm}_{\lambda},\;\lambda\in\mathop{\mathrm{CPar(n)}}\), we write \(\lambda^{\pm}\) in place of \(D^{\pm}_{\lambda}\). Now, we consider the following sum: \[\label{eq:P-P39-comp}
\mathscr{S}um(n):=\sum_{\rho\in\widehat{A_n}}d_{\rho} \mathop{\mathrm{\mathbf{Tally}}}_{\rho}=\sum_{\lambda\in\mathop{\mathrm{NCPar(n)}}}d_{\lambda} \mathop{\mathrm{\mathbf{Tally}}}_{\lambda}+\sum_{\lambda\in\mathop{\mathrm{CPar(n)}}}\left(d_{\lambda^+}
\mathop{\mathrm{\mathbf{Tally}}}_{\lambda^+}+d_{\lambda^-} \mathop{\mathrm{\mathbf{Tally}}}_{\lambda^-}\right),\tag{55}\] and prove the following lemma.
Lemma 10. Let \(\lambda\in\mathop{\mathrm{NCPar(n)}}\), and set \(\alpha:=\left(n-\frac{3}{2}\right)(\log n+c),\;\beta:=\frac{1}{2}(n-1)(\log n+c)\). Then, \(\mathop{\mathrm{\mathbf{Tally}}}_{\lambda}=\mathop{\mathrm{trace}}\left(\left(\widehat{P}(\lambda)\right)^{\left\lceil\alpha\right\rceil}-\left(\widehat{P'}(\lambda)\right)^{\left\lceil\beta\right\rceil}\right)^2\nonumber\)
is less than or equal to the following: \[\begin{align}
&\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))=c(b_T(n-1))+1}}\left(\left(\frac{c(b_T(n))+c(b_T(n-1))}{2n-3}\right)^{\left\lceil\alpha\right\rceil}-\left(\frac{c(b_T(n))}{n-1}\right)^{2\left\lceil\beta\right\rceil}\right)^2\\
&+\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))=c(b_T(n-1))-1}}\left(\left(-\frac{c(b_T(n))+c(b_T(n-1))}{2n-3}\right)^{\left\lceil\alpha\right\rceil}-\left(\frac{c(b_T(n))}{n-1}\right)^{2\left\lceil\beta\right\rceil}\right)^2\nonumber\\
&+\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))\neq
c(b_T(n-1))\pm1\\c(b_T(n-1))<c(b_T(n))}}\left(\left(\frac{c(b_T(n))}{n-1}\right)^{4\left\lceil\beta\right\rceil}+\left(\frac{c(b_T(n-1))}{n-1}\right)^{4\left\lceil\beta\right\rceil}+2\left(\frac{c(b_T(n))+c(b_T(n-1))}{2n-3}\right)^{2\left\lceil\alpha\right\rceil}\right).
\end{align}\] Moreover, for \(\lambda\in\mathop{\mathrm{CPar(n)}}\), the same conclusion holds with \(\lambda\) replaced by \(\lambda^{\pm}\).
Proof. Let us denote \(a'_T:=\frac{c(b_T(n))}{2n-3}, b'_T:=\frac{c(b_T(n-1))}{2n-3}, a_T:=\frac{c(b_T(n))}{(n-1)}\), and \(b_T:=\frac{c(b_T(n-1))}{(n-1)}\). Then, using
equations 44 ,45 , 46 , and 47 , we can write \(\mathop{\mathrm{\mathbf{Tally}}}_{\lambda}\) as follows: \[\begin{align}
&\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))=c(b_T(n-1))+1}}\left(\left(a'_T+b'_T\right)^{\left\lceil\alpha\right\rceil}-\left(a_T\right)^{2\left\lceil\beta\right\rceil}\right)^2+\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))=c(b_T(n-1))-1}}\left(\left(-a'_T-b'_T\right)^{\left\lceil\alpha\right\rceil}-\left(a_T\right)^{2\left\lceil\beta\right\rceil}\right)^2\nonumber\\
&\quad+\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))\neq c(b_T(n-1))\pm1\\c(b_T(n-1))<c(b_T(n))}}\mathop{\mathrm{trace}}\left( \begin{pmatrix} 0&a'_T+b'_T\\&\\
a'_T+b'_T&0 \end{pmatrix}^{\left\lceil\alpha\right\rceil}- \begin{pmatrix} a^2_T&\frac{1}{(n-1)}(a_T+b_T)\\&\\ 0&b^2_T \end{pmatrix}^{\left\lceil\beta\right\rceil}\right)^2.
\end{align}\] Thus, the lemma follows directly from 9.
Moreover, for \(\lambda\in\mathop{\mathrm{CPar(n)}}\), the same conclusion holds by substituting \(\lambda\) with \(\lambda^{\pm}\), and using the equations
48 ,49 , 50 , 51 , along with 9. ◻
Lemma 11. Given any \(\varepsilon>0\) and \(c\in\mathbb{R}\), there exist constants \(M=M(c,\varepsilon)>0\) and sufficiently
large \(N=N(c,\varepsilon,M)>M\) such that for all \(n\geq N\), we have the following bound on \(\mathscr{S}um_1(n)\): \[\mathscr{S}um_1(n)=\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\\\lambda_1\leq n-M}}d_{\lambda}\mathop{\mathrm{\mathbf{Tally}}}_{\lambda}+\sum_{\substack{\lambda\in\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq
n-M}}d^+_{\lambda}\mathop{\mathrm{\mathbf{Tally}}}_{\lambda^+}+\sum_{\substack{\lambda\in\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq n-M}}d^-_{\lambda}\mathop{\mathrm{\mathbf{Tally}}}_{\lambda^-}<\frac{\varepsilon}{2}.\]
Proof. The proof is similar to that of 5. For \(\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\)
and \(T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\), we have \(\left|\frac{c(b_T(n))+c(b_T(n-1))}{2n-3}\right|\leq \frac{2\lambda_1-3}{2n-3}\leq
1,\;\left|\frac{c(b_T(n-1))}{n-1}\right|\leq \frac{\lambda_1-1}{n-1}\leq 1\), and \(\left|\frac{c(b_T(n))}{n-1}\right|\leq \frac{\lambda_1-1}{n-1}\leq 1\). Recall \(\alpha:=\left(n-\frac{3}{2}\right)(\log n+c)\) and \(\beta:=\frac{1}{2}(n-1)(\log n+c)\). Then, for \[\rho\in\{D_{\lambda}:\lambda\in\mathop{\mathrm{NCPar(n)}}\}\bigcup\{D^-_{\lambda},D^+_{\lambda}:\lambda\in\mathop{\mathrm{CPar(n)}}\},\] using \((a-b)^2\leq 2(a^2+b^2)\) for \(a,b\in\mathbb{R}\), 10 implies \[\begin{align}
\mathop{\mathrm{\mathbf{Tally}}}_{\rho}\leq&\;2\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))=c(b_T(n-1))\pm1}}\left(\left(\frac{2\lambda_1-3}{2n-3}\right)^{2\left\lceil\alpha\right\rceil}+\left(\frac{\lambda_1-1}{n-1}\right)^{4\left\lceil\beta\right\rceil}\right)\nonumber\\
&\quad\quad+\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))\neq
c(b_T(n-1))\pm1\\c(b_T(n-1))<c(b_T(n))}}2\left(\left(\frac{\lambda_1-1}{n-1}\right)^{4\left\lceil\beta\right\rceil}+\left(\frac{2\lambda_1-3}{2n-3}\right)^{2\left\lceil\alpha\right\rceil}\right) \nonumber\\
\leq&\;2\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\left(\frac{2\lambda_1-3}{2n-3}\right)^{2\left\lceil\alpha\right\rceil}+\left(\frac{\lambda_1-1}{n-1}\right)^{4\left\lceil\beta\right\rceil}\right)
\tag{56}\\ \leq &\;2\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(\left(\frac{2\lambda_1-3}{2n-3}\right)^{2\alpha}+\left(\frac{\lambda_1-1}{n-1}\right)^{4\beta}\right),\text{ using
}\alpha\leq\lceil\alpha\rceil\text{ and }\beta\leq\lceil\beta\rceil \nonumber\\ \leq
&\;2\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}\left(e^{-\frac{4\alpha(n-\lambda_1)}{2n-3}}+e^{-\frac{4\beta(n-\lambda_1)}{n-1}}\right),\text{ using }1-x\leq e^{-x}\text{ for all }x\geq 0 \nonumber\\ \leq
&\;2\sum_{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}}2e^{-2(n-\lambda_1)(\log n+c)},\text{ writing the values of }\alpha\text{ and }\beta \nonumber\\ =&\begin{cases} d_{\lambda}\times 4e^{-2(n-\lambda_1)(\log
n+c)}&\text{ if }\rho=D_{\lambda},\\ d^{\pm}_{\lambda}\times 4e^{-2(n-\lambda_1)(\log n+c)}&\text{ if }\rho=D^{\pm}_{\lambda}. \end{cases}\tag{57}
\end{align}\] The inequality in 56 follows from \(\left(\frac{2\lambda_1-3}{2n-3}\right)^2\leq 1,\left(\frac{\lambda_1-1}{n-1}\right)^4\leq 1,\alpha\leq\lceil\alpha\rceil,\beta\leq\lceil\beta\rceil\), and the following facts:
\(\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\) is a disjoint union of \(\{T:c(b_T(n))= c(b_T(n-1))\pm1\}\) and \(\{T:c(b_T(n))\neq c(b_T(n-1))\pm1\}\).
We rewrite the following from 57 : \[\mathop{\mathrm{\mathbf{Tally}}}_{\rho}=\mathop{\mathrm{trace}}\left(\left(\widehat{P}(\rho)\right)^{\left\lceil\alpha\right\rceil}-\left(\widehat{P'}(\rho)\right)^{\left\lceil\beta\right\rceil}\right)^2\leq \begin{cases}
d_{\lambda}\times 4e^{-2(n-\lambda_1)(\log n+c)}&\text{ if }\rho=D_{\lambda},\\ d^{\pm}_{\lambda}\times 4e^{-2(n-\lambda_1)(\log n+c)}&\text{ if }\rho=D^{\pm}_{\lambda}. \end{cases}\] Now, choose a sufficiently large positive integer \(M=M(c,\varepsilon)\) such that \(\displaystyle\sum_{m\geq M}\frac{e^{-2mc}}{m!}<\frac{\varepsilon}{8}\). Then, for \(n\geq N=M+1\), we have that
\[\begin{align} \mathscr{S}um_1(n)\leq &\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\\\lambda_1\leq n-M}}4d_{\lambda}^2e^{-2(n-\lambda_1)(\log
n+c)}+\sum_{\substack{\lambda\in\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq n-M}}4\left((d^+_{\lambda})^2+(d^-_{\lambda})^2\right)e^{-2(n-\lambda_1)(\log n+c)}\nonumber\\ <&\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\\\lambda_1\leq
n-M}}4d_{\lambda}^2e^{-2(n-\lambda_1)(\log n+c)}+\sum_{\substack{\lambda\in\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq n-M}}4d_{\lambda}^2e^{-2(n-\lambda_1)(\log n+c)}\tag{58}\\ \leq&\sum_{\lambda\vdash n:\;\lambda_1\leq
n-M}4d_{\lambda}^2e^{-2(n-\lambda_1)(\log n+c)}\tag{59}\\ \leq\;&4\sum_{m=M}^{n-1}\frac{e^{-2mc}}{m!}<4\sum_{m\geq M}\frac{e^{-2mc}}{m!}<\frac{\varepsilon}{2}.\tag{60}
\end{align}\] The inequality in 58 follows from the fact that \((d^+_{\lambda})^2+(d^-_{\lambda})^2=2\left(\frac{d_{\lambda}}{2}\right)^2<d_{\lambda}^2\). The inequality in 59
follows from the fact that \(\displaystyle\sum_{\substack{\lambda\notin\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\\lambda_1\leq n-M}}4d_{\lambda}^2e^{-2(n-\lambda_1)(\log n+c)}\geq 0\). Finally, the first
inequality in 60 follows from the same reasoning as in 21 – 23 . This completes the proof. ◻
Lemma 12. Given any \(\varepsilon>0\) and \(c\in\mathbb{R}\), recall \(M\) from 11. Then, we have the following: \[\displaystyle\lim_{n\rightarrow\infty}\mathscr{S}um_2(n)=0,\]\[\text{ where }
\mathscr{S}um_2(n)=\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\\n-M\leq\lambda_1< n}}d_{\lambda}\mathop{\mathrm{\mathbf{Tally}}}_{\lambda}+\sum_{\substack{\lambda\in\mathop{\mathrm{CPar(n)}}\\n-M\leq\lambda_1<
n}}d^+_{\lambda}\mathop{\mathrm{\mathbf{Tally}}}_{\lambda^+}+\sum_{\substack{\lambda\in\mathop{\mathrm{CPar(n)}}\\n-M\leq\lambda_1< n}}d^-_{\lambda}\mathop{\mathrm{\mathbf{Tally}}}_{\lambda^-}.\]
Proof. For \(\lambda\vdash n\), we recall the partition of \(\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\) from the proof of 6. More precisely, the set \(\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\) is partitioned into two
subsets as follows: \[\begin{align} \mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)&=\{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}:\text{ both }n-1\text{ and }n\text{ are in the first row of
}T\}.\\ \mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)&=\{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}:\;n-1\text{ or }n\text{ is below the first row of }T\}\\
&=\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\setminus\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda).
\end{align}\] For the rest of this proof, we work with \(\lambda\in\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\) satisfying \(n-M\leq\lambda_1<n\). From the proof of 6, we recall the following: \[\begin{align} |\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)|&\leq\begin{cases}
d_{\lambda}&\text{ for non-self-conjugate }\lambda,\\ \frac{d_{\lambda}}{2}&\text{ for self-conjugate }\lambda, \end{cases}\tag{61}\\ |\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)|&\leq\begin{cases}
\frac{M\times4^{n-\lambda_1}}{n}d_{\lambda}\leq \frac{M\times4^{M}}{n}d_{\lambda}&\text{ for non-self-conjugate }\lambda,\\ \frac{M\times4^{n-\lambda_1}}{n}\frac{d_{\lambda}}{2}\leq \frac{M\times4^{M}}{n}\frac{d_{\lambda}}{2}&\text{ for
self-conjugate }\lambda. \end{cases}\tag{62}
\end{align}\] From 10,
let us recall the notations \(\alpha=\left(n-\frac{3}{2}\right)(\log n+c),\beta=\frac{1}{2}(n-1)(\log n+c)\), \(a'_T=\frac{c(b_T(n))}{2n-3},
b'_T=\frac{c(b_T(n-1))}{2n-3},a_T=\frac{c(b_T(n))}{(n-1)}\), and \(b_T=\frac{c(b_T(n-1))}{(n-1)}\). Therefore, using 10, for \(\rho\in\{\lambda:\lambda\in\mathop{\mathrm{NCPar(n)}}\}\cup\{\lambda^+,\lambda^-:\lambda\in\mathop{\mathrm{CPar(n)}}\}\), we get that
\[\begin{align}
\mathop{\mathrm{\mathbf{Tally}}}_{\rho}\leq&\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))=c(b_T(n-1))+1}}\left(\left(a'_T+b'_T\right)^{\left\lceil\alpha\right\rceil}
-\left(a_T\right)^{2\left\lceil\beta\right\rceil}\right)^2+
\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))=c(b_T(n-1))-1}}\left(\left(-a'_T-b'_T\right)^{\left\lceil\alpha\right\rceil}-\left(a_T\right)^{2\left\lceil\beta\right\rceil}\right)^2\nonumber\\
&\quad\quad+\sum_{\substack{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\\c(b_T(n))\neq c(b_T(n-1))\pm1 \\c(b_T(n-1))<c(b_T(n))}}\left((a_T)^{4\left\lceil\beta\right\rceil}+(b_T)^{4\left\lceil\beta\right\rceil}
+2(a'_T+b'_T)^{2\left\lceil\alpha\right\rceil}\right) \nonumber\\
\leq&\sum_{T\in\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)}\left(\left(a'_T+b'_T\right)^{\left\lceil\alpha\right\rceil}-\left(a_T\right)^{2\left\lceil\beta\right\rceil}\right)^2+\sum_{\substack{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)\\c(b_T(n))=c(b_T(n-1))\pm1}}\left(|a'_T+b'_T|^{\left\lceil\alpha\right\rceil}+|a_T|^{2\left\lceil\beta\right\rceil}\right)^2\label{eq:Main-term392}\\
&\quad\quad+\sum_{\substack{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)\\c(b_T(n))\neq
c(b_T(n-1))\pm1\\c(b_T(n-1))<c(b_T(n))}}\left((a_T)^{4\left\lceil\beta\right\rceil}+(b_T)^{4\left\lceil\beta\right\rceil}+2(a'_T+b'_T)^{2\left\lceil\alpha\right\rceil}\right).\nonumber
\end{align}\tag{63}\] The inequality in 63 follows from the triangle inequality and the fact that \(\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)\) is a subset of \(\{T\in\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}:c(b_{T}(n))=c(b_{T}(n-1))+1\}\). Thus, we have \(a'_T+b'_T=\frac{2\lambda_1-3}{2n-3}\) and \(a_T=\frac{\lambda_1-1}{n-1}\) for \(T\in\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)\). Additionally, \(|a'_T+b'_T|\leq
\left|\frac{2\lambda_1-3}{2n-3}\right|\leq 1\) and \(|a_T|\leq \left|\frac{\lambda_1-1}{n-1}\right|\leq 1\) for \(T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)\). Hence, we have the
following: \[\begin{align}
\label{eq:Main-term393} (a'_T+b'_T)^{\lceil\alpha\rceil}-(a_T)^{2\lceil\beta\rceil}&=\left(\frac{2\lambda_1-3}{2n-3}\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}-\left(\frac{\lambda_1-1}{n-1}\right)^{2\lceil\frac{1}{2}(n-1)(\log
n+c)\rceil}\\ &=e^{-(n-\lambda_1)(\log n+c)}o(1),\text{ for }T\in\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda).\nonumber
\end{align}\tag{64}\] Also, using \(\alpha\leq\lceil\alpha\rceil\) and \(\alpha\leq\lceil\beta\rceil\), we obtain the following: \[\begin{align} &|a'_T+b'_T|^{\lceil\alpha\rceil}\leq \left(\frac{2\lambda_1-3}{2n-3}\right)^{\lceil\left(n-\frac{3}{2}\right)(\log n+c)\rceil}\leq \left(\frac{2\lambda_1-3}{2n-3}\right)^{\left(n-\frac{3}{2}\right)(\log
n+c)}\leq e^{-(n-\lambda_1)(\log n+c)},\tag{65}\\ &|a_T|^{2\lceil\beta\rceil},|b_T|^{2\lceil\beta\rceil}\leq \left(\frac{\lambda_1-1}{n-1}\right)^{2\lceil\frac{n-1}{2}(\log n+c)\rceil}\leq \left(\frac{\lambda_1-1}{n-1}\right)^{(n-1)(\log n+c)}\leq
e^{-(n-\lambda_1)(\log n+c)},\tag{66}
\end{align}\] for \(T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)\). Therefore, using the
estimates from 64 , 65 , and 66 in 63 , we get that \[\begin{align}
\mathop{\mathrm{\mathbf{Tally}}}_{\rho}\leq&\sum_{T\in\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)}\left(e^{-(n-\lambda_1)(\log
n+c)}o(1)\right)^2+\sum_{\substack{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)\\c(b_T(n))=c(b_T(n-1))\pm1}}\left(2e^{-(n-\lambda_1)(\log n+c)}\right)^2\nonumber\\ &\quad+\sum_{\substack{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)\\c(b_T(n))\neq
c(b_T(n-1))\pm1\\c(b_T(n-1))<c(b_T(n))}}\left(e^{-2(n-\lambda_1)(\log n+c)}+e^{-2(n-\lambda_1)(\log n+c)}+2e^{-2(n-\lambda_1)(\log n+c)}\right)\nonumber\\ \leq&\sum_{T\in\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)}e^{-2(n-\lambda_1)(\log
n+c)}\left(o(1)\right)^2+\sum_{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)}\left(2e^{-(n-\lambda_1)(\log n+c)}\right)^2 \tag{67}\\ \leq&\begin{cases} \left(\left(o(1)\right)^2+\frac{M\times 4^{M+1}}{n}\right)d_{\lambda}e^{-2(n-\lambda_1)(\log
n+c)}&\text{ if }\rho=D_{\lambda},\lambda\text{ is non-self-conjugate},\\ \left(\left(o(1)\right)^2+\frac{M\times 4^{M+1}}{n}\right)\frac{d_{\lambda}}{2}e^{-2(n-\lambda_1)(\log n+c)}&\text{ if }\rho=D^{\pm}_{\lambda},\lambda\text{ is
self-conjugate}. \end{cases}\tag{68}
\end{align}\] The inequality in 67 follows from the following facts:
\(\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)\) is a disjoint union of \(\{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda):c(b_T(n))= c(b_T(n-1))\pm1\}\) and \(\{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda):c(b_T(n))\neq c(b_T(n-1))\pm1\}\).
The set \(\Big\{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda):c(b_T(n))\neq c(b_T(n-1))\pm1\Big\}\) contains the set \(\\\Big\{T\in\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda):c(b_T(n))\neq
c(b_T(n-1))\pm1,\;c(b_T(n-1))< c(b_T(n)) \Big\}\).
The inequality in 68 follows from the bounds in 61 and 62 , which provide estimates for the number of elements in \(\mathop{\mathrm{\mathcal{S}^{MT}}}(\lambda)\) and \(\mathop{\mathrm{\mathcal{S}^{ET}}}(\lambda)\). Now, using the estimates obtained in 68 and the fact that
\(d_{\lambda}^+=d_{\lambda}^-=\frac{d_{\lambda}}{2}\), we get that \[\begin{align} \mathscr{S}um_2(n)&\leq
\sum_{\substack{\lambda\in\mathop{\mathrm{NCPar(n)}}\\n-M\leq\lambda_1<n}}d_{\lambda}^2\left(\left(o(1)\right)^2+\frac{M\times 4^{M+1}}{n}\right)e^{-2(n-\lambda_1)(\log n+c)}\nonumber\\
&\quad+2\sum_{\substack{\lambda\in\mathop{\mathrm{CPar(n)}}\\n-M\leq\lambda_1<n}}\left(\frac{d_{\lambda}}{2}\right)^2\left(\left(o(1)\right)^2+\frac{M\times 4^{M+1}}{n}\right)e^{-2(n-\lambda_1)(\log n+c)}\nonumber\\ &<\sum_{\lambda\vdash
n\;:\;n-M\leq\lambda_1<n}d_{\lambda}^2\left(\left(o(1)\right)^2+\frac{M\times 4^{M+1}}{n}\right)e^{-2(n-\lambda_1)(\log n+c)}.\label{eq:Main-term396}
\end{align}\tag{69}\] The inequality in 69 follows from the fact that: \(\frac{d^2_{\lambda}}{2}<d_{\lambda}^2\), and \[\sum_{\substack{\lambda\notin\mathop{\mathrm{NCPar(n)}}\cup\mathop{\mathrm{CPar(n)}}\\n-M\leq\lambda_1<n}}d_{\lambda}^2\left(\left(o(1)\right)^2+\frac{M\times 4^{M+1}}{n}\right)e^{-2(n-\lambda_1)(\log n+c)}\geq 0.\] We now
perform similar calculations to those done in 3334 but replacing \((o(1))^2\) in place of \((e^{o(1)}-1)^2\). This gives the
following inequality: \[\label{eq:Main-term397} \sum_{\lambda\vdash n\;:\;n-M\leq\lambda_1<n}d_{\lambda}^2e^{-2(n-\lambda_1)(\log
n+c)}\left(o(1)\right)^2<\left(e^{e^{-2c}}-1\right)\left(o(1)\right)^2.\tag{70}\] Next, we perform similar calculations to those in 3738 , but replacing \((e^{o(1)}+1)^2\) with \(4\), and obtain: \[\label{eq:Main-term398} \sum_{\lambda\vdash
n\;:\;n-M\leq\lambda_1<n}\frac{M\times 4^M}{n}\;d_{\lambda}^2e^{-2(n-\lambda_1)(\log n+c)}\times 4<\frac{M\times 4^M}{n}\left(e^{e^{-2c}}-1\right)\times 4.\tag{71}\] Finally, combining the inequalities from 69 ,70 , and 71 , we arrive at the following: \[0\leq\mathscr{S}um_2(n)<\left(e^{e^{-2c}}-1\right)\left((o(1))^2+\frac{M\times
4^{M+1}}{n}\right).\] Thus, the lemma follows from the fact \(\left(e^{e^{-2c}}-1\right)\left((o(1))^2+\frac{M\times 4^{M+1}}{n}\right)\rightarrow 0\) as \(n\rightarrow\infty\). ◻
Following the notations of 12, we note down an immediate corollary as follows:
Corollary 13. There exists a large enough positive integer \(\overline{N}=\overline{N}(c,\varepsilon,M)>0\) such that for all \(n\geq \overline{N}\), we have \(\mathscr{S}um_2(n)<\frac{\varepsilon}{2}\).
Using 11 and 13, we obtain that \(\mathscr{S}um(n)=\mathscr{S}um_1(n)+\mathscr{S}um_2(n)<\varepsilon\) for all \(n\geq \max\{N,\overline{N}\}\), where \(\mathscr{S}um(n)\) is given in 55 . Since \(\varepsilon>0\) is arbitrary, we conclude that \(\displaystyle\lim_{n\rightarrow\infty}\mathscr{S}um(n)=0\). Therefore, using 2 and 1, we conclude that: \[\lim_{n\rightarrow\infty}\left\|(P')^{*\lceil\frac{1}{2}(n-1)\log n+cn\rceil}-U_{A_n}\right\|_{\text{TV}}=d_{\text{TV}}\left(\text{Poi}(1+e^{-c}),\text{Poi}(1)\right),\;c\in\mathbb{R}.\]
Remark 4. Although Nestoridi’s comparison method fails to compare the random walks on \(A_n\) driven by \(P'\) and \(P\), it applies
nicely to the comparison between the random walks on \(A_n\) driven by \(P'\) and \(Q\). The proof technique for comparing these latter walks uses
symmetric group character estimates and proceeds similarly to the argument presented in 4. Here, we directly compare the random walks on \(A_n\) driven by \(P'\) and \(P\) to illustrate our comparison method (2) for random walks with a non-commuting
transition matrix.
We sincerely thank the anonymous referees for their valuable comments, which have significantly improved the quality of this article. We also extend our gratitude to Evita Nestoridi and Raghavendra Tripathi for their insightful feedback on the previous
version of the manuscript. SG acknowledges the support of the INSPIRE FACULTY FELLOW research grant (IFA 23 MA 198).
Subhajit Ghosh. Total variation cutoff for the transpose top-2 with random shuffle. J. Theoret. Probab., 33(4):1832–1854, 2020.
[2]
Jung Sing Jwo, S. Lakshmivarahan, and S. K. Dhall. A new class of interconnection networks based on the alternating group. Networks, 23(4):315–326, 1993.
[3]
Eddie Cheng and Marc J. Lipman. Vulnerability issues of star graphs, alternating group graphs and split-stars: strength and toughness. Discrete Appl. Math., 118(3):163–179,
2002.
[4]
Xueyi Huang and Qiongxiang Huang. The second largest eigenvalues of some Cayley graphs on alternating groups. J. Algebraic Combin., 50(1):99–111, 2019.
[5]
Yanze Huang, Limei Lin, and Dajin Wang. On the reliability of alternating group graph-based networks. Theoret. Comput. Sci., 728:9–28, 2018.
[6]
Yanze Huang, Limei Lin, Li Xu, and Xiaoding Wang. Extra diagnosability and good-neighbor diagnosability of \(n\)-dimensional alternating
group graph \(AG_n\) under the PMC model. Theoret. Comput. Sci., 795:36–49, 2019.
[7]
Lantao You, Jianxi Fan, Yuejuan Han, and Xiaohua Jia. One-to-one disjoint path covers on alternating group graphs. Theoret. Comput. Sci., 562:146–164, 2015.
[8]
Jin-Xin Zhou. The automorphism group of the alternating group graph. Appl. Math. Lett., 24(2):229–231, 2011.
[9]
S Lakshmivaraha and Sudarshan K Dhall. Analysis and design of parallel algorithms: Arithmetic and matrix problems. McGraw-Hill, Inc., 1990.
[10]
Persi Diaconis and Mehrdad Shahshahani. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete, 57(2):159–179, 1981.
[11]
David Aldous and Persi Diaconis. Shuffling cards and stopping times. Amer. Math. Monthly, 93(5):333–348, 1986.
[12]
David Aldous and Persi Diaconis. Strong uniform times and finite random walks. Adv. in Appl. Math., 8(1):69–97, 1987.
[13]
Persi Diaconis. Applications of non-commutative fourier analysis to probability problems. In École d’Été de Probabilités de
Saint-Flour XV–XVII, 1985–87, pages 51–100. Springer, 1988.
[14]
Persi Diaconis. Group representations in probability and statistics. 11:vi+198, 1988.
[15]
David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and
David B. Wilson.
[16]
Laurent Saloff-Coste. Random walks on finite groups. In Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 263–346. Springer, Berlin,
2004.
[17]
Persi Diaconis, Ronald L. Graham, and John A. Morrison. Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures & Algorithms, 1(1):51–72,
1990.
[18]
Evita Nestoridi and Sam Olesker-Taylor. Limit profiles for reversible Markov chains. Probab. Theory Related Fields, 182(1-2):157–188, 2022.
[19]
Dave Bayer and Persi Diaconis. Trailing the dovetail shuffle to its lair. Ann. Appl. Probab., 2(2):294–313, 1992.
[20]
Alexey Bufetov and Peter Nejjar. Cutoff profile of ASEP on a segment. Probab. Theory Related Fields, 183(1-2):229–253, 2022.
[21]
Hubert Lacoin. The cutoff profile for the simple exclusion process on the circle. Ann. Probab., 44(5):3399–3430, 2016.
[22]
Sam Olesker-Taylor and Dominik Schmid. Limit profile for the Bernoulli–Laplace urn. arXiv preprint arXiv:2409.07900, 2024.
[23]
Evita Nestoridi and Sam Olesker-Taylor. Limit profiles for projections of random walks on groups. Electron. J. Probab., 29:Paper No. 158, 22, 2024.
[24]
Jonathan Hermon and Sam Olesker-Taylor. Cutoff for almost all random walks on abelian groups. arXiv preprint arXiv:2102.02809, 2021.
[25]
Eyal Lubetzky and Yuval Peres. Cutoff on all Ramanujan graphs. Geom. Funct. Anal., 26(4):1190–1216, 2016.
[26]
Lucas Teyssier. Limit profile for random transpositions. Ann. Probab., 48(5):2323–2343, 2020.
[27]
Evita Nestoridi. Comparing limit profiles of reversible Markov chains. Electron. J. Probab., 29:Paper No. 58, 14, 2024.
[28]
Jean Delhaye. Brownian motion on the unitary quantum group: construction and cutoff. arXiv preprint arXiv:2409.06552, 2024.
[29]
Vishesh Jain and Mehtaab Sawhney. Hitting time mixing for the random transposition walk. arXiv preprint arXiv:2410.23944, 2024.
[30]
Robin Pemantle. A shuffle that mixes sets of any fixed size much faster than it mixes the whole deck. Random Structures Algorithms, 5(5):609–626, 1994.
[31]
Oded Schramm. Compositions of random transpositions. Israel J. Math., 147:221–243, 2005.
[32]
Jean-Pierre Serre. Linear representations of finite groups. Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott, Graduate
Texts in Mathematics, Vol. 42.
[33]
Gordon James and Adalbert Kerber. The representation theory of the symmetric group, volume 16 of Encyclopedia of Mathematics and its Applications. Addison-Wesley
Publishing Co., Reading, Mass., 1981. With a foreword by P. M. Cohn, With an introduction by Gilbert de B. Robinson.
[34]
Bob Hough. The random \(k\) cycle walk on the symmetric group. Probab. Theory Related Fields, 165(1-2):447–482, 2016.
[35]
Oliver Ruff. Weight theory for alternating groups. Algebra Colloq., 15(3):391–404, 2008.
Note that \(\mathop{\mathrm{UStd(\lambda)}}=\mathop{\mathrm{UStd(\lambda)}}\cup\mathop{\mathrm{UStd(\lambda^{\prime})}}\) for all self-conjugate \(\lambda\vdash
n\).↩︎