%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{6}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\DeclareMathOperator{\Diag}{Diag}
\DeclareMathOperator{\Fix}{Fix}
\DeclareMathOperator{\Poiss}{Poiss}
\DeclareMathOperator{\Flip}{Flip}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\Eig}{Eig}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Zone}{Zone}
\newcommand{\fS}{\mathfrak{S}}

\newcommand{\TV}{\mathsf{TV}}
\newtheorem{thm}[equation]{Theorem}
\newtheorem{lem}[equation]{Lemma}
\newtheorem{prop}[equation]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[equation]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[equation]{Remark}

\usepackage{lipsum}
\usepackage{mathrsfs}
\usepackage{tikz}
\usepackage{pgfplots}
\pgfplotsset{compat=1.18}

%% define your title in the usual way
\title{Cutoff for the Biased Random Transposition Shuffle}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[E. Nestoridi and A. Yan]{\texorpdfstring{Evita Nestoridi\thanks{\href{mailto:evrydiki.nestoridi@stonybrook.edu}{evrydiki.nestoridi@stonybrook.edu}. Partially supported by NSF grant DMS-2346986}\addressmark{1} \and Alan Yan\thanks{\href{mailto:alanyan@math.harvard.edu}{alanyan@math.harvard.edu}}\addressmark{2}}{Evita Nestoridi and Alan Yan}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1} Mathematics Department, Stony Brook University, Stony Brook NY, 11794-3651, USA \\ \addressmark{2} Department of Mathematics, Harvard University, Cambridge MA, 02138, USA}

%% put the date of submission here
\received{November 14th, 2024}

%% leave this blank until submitting a revised version
\revised{March 31st, 2025}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We study the biased random transposition shuffle, a natural generalization of the classical random transposition shuffle studied by Diaconis and Shahshahani. Using the representation theory of the symmetric group, we diagonalize the transition matrix of the shuffle. We use these eigenvalues to prove that the shuffle exhibits total variation cutoff at time $t_N = \frac{1}{2b} N \log N$ with window $N$. We also prove that the limiting distribution of the number of fixed cards near the cutoff time is Poisson.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{symmetric group, partitions, Littlewood--Richardson coefficients, cutoff phenomenon, hive models, card shuffling}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above



\section{Introduction}

The study of card shuffling with the help of representation theory was initially introduced by Diaconis and Shahshahani~\cite{Diaconis1981} for the random transpositions shuffle. In this shuffle, consider a deck of $N$ distinct cards. Pick two cards uniformly at random with repetition and swap them. Diaconis and Shahshahani proved that it takes $\frac{1}{2} N \log N$ repetitions until the deck is shuffled sufficiently well. This model is now famously known as the \emph{random transpositions shuffle}, and to this day, it is considered the best approximation of the Markov chain that genes in DNA sequences follow~\cite{BeDu}. Following Diaconis and Shahshahani, there has been a variety of other card shuffles that have been studied with the use of representation theory (see~\cites{Flatto1985, Hough2016, Dieker2018, BernsteinNestoridi2019, BateConnorMatheau-Raven2021,NestoridiPeng2021, Bidigare-Hanlon-Rockmore-1999, BrownDiaconis1998}).


In this extended abstract, we consider a generalization of random transpositions, where we partition the cards into two sets and pick cards with probabilities depending on which half of the deck they belong. More precisely, consider a deck of $N=2n$ distinct cards and denote $[N]:= \{1, \ldots, N\}$. We partition the cards into two sets $[N] = A \sqcup B$. Fix numbers $0 < b \leq a$ satisfying $a |A| + b |B| = N$. Let $\mu_{a, b}$ be the probability measure on $[N]$ given by 
\[
    \mu_{a, b}(x) = \begin{cases}
        \frac{a}{N} & \text{ if } x \in A \\
        \frac{b}{N} & \text{ if } x \in B. 
    \end{cases}
\]
We pick two cards uniformly at random with repetition according to $\mu_{a, b}$ and swap them. By identifying all of the configurations of our deck with elements in $\mathfrak{S}_N$, we can think of the shuffle as a random walk on $\mathfrak{S}_N$. 
%Since the distribution of our deck configuration before performing a shuffle is only dependent on the current deck configuration, we can view our shuffle as a \emph{(discrete time) Markov chain} on $\fS_N$. 
%This shuffling scheme was studied in~\cite{Bernstein2017} where it was called the \emph{biased transposition shuffle}. 
We refer to it as the \textbf{biased random transpositions shuffle} to emphasize its connection to the classical case of random transpositions considered in~\cite{Diaconis1981}. Indeed, in the case $a=b=1$, we recover the original random transposition shuffle.  

For $x \in \mathfrak{S}_N$, let $P^t(x, \bullet)$ be the distribution of our deck configuration after $t$ shuffles starting from the initial configuration $x$. For two probability measures $\mu, \nu$ on $\mathfrak{S}_N$, let $d_{\TV}(\mu, \nu)$ be the \textbf{total variation distance} between $\mu$ and $\nu$. Explicitly, the total variation distance is equal to 
\[
    d_{\TV} (\mu, \nu) := \frac{1}{2} \sum_{x \in \mathfrak{S}_N} |\mu(x) - \nu(x)|.
\]
We prove that the biased random transposition shuffle exhibits \textbf{total variation distance cutoff} at time $\frac{1}{2b} N \log N$ by diagonalizing the transition matrix $P=(P(x, y))_{x,y \in \mathfrak{S}_N}$ and using this spectral information to produce lower and upper bounds for the mixing time. We are ready to state our main result, where for simplicity we assume $N = 2n$ is even. 

\begin{thm} \label{thm:main-theorem-1}
    Let $|A| = |B| = n$. Let $c > 0$ be a positive real number. For sufficiently large $N$ and some universal constant $C > 0$, we have
     \begin{align*}
        d_{\mathsf{TV}} \left ( P^{\frac{N}{2b}(\log N + c)}(\text{id}, \cdot), U \right ) & \leq C \cdot e^{-c} 
        \quad \text{ and } \\
        d_{\mathsf{TV}} \left ( P^{\frac{N}{2b}(\log N - c)}(\text{id}, \cdot), U \right ) & \geq 1 - e^{- \frac{1}{2} \left ( \sqrt{1 + \frac{1}{2} e^c} - 1 \right )^2} + o(1),
    \end{align*}
    where $U$ is the uniform measure on $\mathfrak{S}_N$. 
\end{thm}

\Cref{thm:main-theorem-1} describes the occurrence of the \textbf{cutoff phenomenon}. A family of Markov chains on $\mathfrak{S}_N$ is said to have (total variation) cutoff at $t_N$ with window $w_N=o(t_N)$ if
\[
    \lim_{c \rightarrow \infty} \lim_{N \rightarrow \infty} d(t_N-cw_N)= 1 \quad\mbox{ and }\quad \lim_{c \rightarrow \infty} \lim_{N \rightarrow \infty} d(t_N+cw_N)= 0.
\]
\Cref{fig:cutoff} is a schematic picture of the cutoff phenomenon. The curve shown is the graph of the function $d(t)$ representing the total variation distance from our deck of cards at time $t$ to the uniform distribution. The cutoff phenomenon concerns the curve outside of the window $[t_N - cw_N, t_N + cw_N]$, specifically its convergence to a step function. The question about the limiting curve of $d(t)$ within the window $[t_N - cw_N, t_N + cw_N]$ concerns the \textbf{limit profile}. In this extended abstract, we do not discuss the limit profile and direct the interested reader to~\cite{preprint}. 

\begin{figure}[ht]
    \begin{center}
    \begin{tikzpicture}[scale = 5]
        \definecolor{lightblue}{rgb}{0.68, 0.85, 0.90}

        \draw[->, line width=0.25mm] (0,0) -- (1.2,0) node[right] {$t$};
        \draw[->, line width=0.25mm] (0,0) -- (0,1.2) node[left] {$d(t)$};

        \draw[scale=1, domain=0:1, smooth, variable=\x, blue, thick] 
        plot ({\x}, {1 - exp(-0.5 * exp(-18 * (\x - 0.5)))});
        \draw[dashed] (0.35,0) -- (0.35, 1.1);
        \draw[dashed] (0.75,0) -- (0.75, 1.1);
        \draw (0.55,-0.03) -- (0.55, 0.03);
        \node at (0.55,-0.07) {$t_N$};
        \node at (0.85,-0.07) {$t_N + cw_N$};
        \node at (0.25,-0.07) {$t_N - cw_N$};
    \end{tikzpicture}
    \end{center}
    \caption{The cutoff phenomenon}\label{fig:cutoff}
\end{figure}

The occurrence of cutoff is a central question in Markov chain mixing, see more in \cite{Salez}. The first instances of cutoff were in card shuffling in works by Aldous, Diaconis and Shahshahani \cites{Aldous, Diaconis1981}, and since then cutoff has been studied in terms of many other card shuffles \cites{Bayer, Bese, BernsteinNestoridi2019, Hough2016, Lacoin}. 

The biased random transposition shuffle was also studied in \cite{Bernstein2017}, where the authors focused on separation distance. Their proof relied on analyzing the behavior of a stopping time, that unfortunately turned out not to be a strong stationary time as explained in Section 5.3 of \cite{Graham}. In this paper, we follow a spectral approach to prove the behavior that was predicted in \cite{Bernstein2017}.

The upper bound of \Cref{thm:main-theorem-1} is proven by an $\ell_2$-bound, which makes use of the eigenvalues of the transition matrix $P$. Our second theorem explicitly describes the eigenvalue spectrum of $P$. The statement involves the \textbf{diagonal index} of a partition $\lambda$, defined to be
\[
    \Diag(\lambda) := \sum_{i \geq 0} \binom{\lambda_i}{2} - \sum_{i \geq 0} \binom{\lambda_i^*}{2}. 
\]
Here, $\lambda^*$ is the partition conjugate to $\lambda$. The eigenvalue spectrum of $P$ is given by the following theorem.
\begin{thm}\label{thm:main-theorem-3}
    The transition matrix $P$ has eigenvalues 
    \[
        \frac{a^2 |A| + b^2 |B|}{N^2} + \frac{2(a^2 - ab)}{N^2} \Diag(\mu) + \frac{2(b^2 -ab)}{N^2} \Diag(\nu) + \frac{2ab}{N^2} \Diag(\lambda),
    \]
    with multiplicities $f_\lambda f_\mu f_\nu c^\lambda_{\mu, \nu}$ for all partitions $\lambda \vdash N$, $\mu \vdash |A|$, and $\nu \vdash |B|$, where $f_\lambda $ is the number of standard Young tableaux of shape $\lambda$ and  $c^\lambda_{\mu, \nu}$ is the Littlewood--Richardson coefficient.
\end{thm}


The lower bound of \Cref{thm:main-theorem-1} is proven by studying the number of fixed cards at time $t$. Let $\Fix_c$ be the number of fixed points after shuffling our deck of cards using the biased random transposition shuffle $\frac{1}{2b} N (\log N - c)$ times. Let $\Fix$ be the number of fixed points of a uniformly chosen permutation. The random variable $\Fix_c$ has the following limiting distribution. 

\begin{thm}\label{thm:main-theorem-4'}
    Suppose that $b < 1$. Then, we have
    \begin{equation}\label{eqn:fix-converges-poisson-yes}
        \Fix_c \xrightarrow{dist} \Poiss \left (1 + \frac{1}{2}e^c \right ), \quad \text{ as } N \to \infty. 
    \end{equation}
    where the convergence is convergence in distribution. Also, we have 
    \begin{equation}\label{eqn:tv-converges-yes}
        d_{\TV} \left ( \Fix_c , \Fix \right ) \longrightarrow d_{\TV} \left ( \Poiss(1), \Poiss \left (1 + \frac{1}{2}e^c \right ) \right ), \quad \text{ as } N \to \infty. 
    \end{equation}
\end{thm}
Note that Equation~\ref{eqn:tv-converges-yes} follows immediately from Equation~\ref{eqn:fix-converges-poisson-yes} by definition of convergence in distribution. \Cref{thm:main-theorem-4'} is analogous to \cite[Equation 1.6]{Matthews1988} which was proven for random transpositions. 

\begin{remark}
    Our proof is motivated by the proof in~\cite{Diaconis1981} for random transpositions. However, in the biased case we run into several  difficulties which require new ideas. Since our shuffle is not conjugacy class invariant, we need another way to diagonalize our shuffle. In terms of the analysis, we need an understanding of the positivity of the Littlewood--Richardson coefficients, which plays no role in random transpositions. Finally, we provide an algebraic proof of the fixed point result of~\cite{Matthews1988} which also generalizes to the biased case. 
\end{remark}

\section{Spectral Analysis}

In this section, we prove \Cref{thm:main-theorem-3}, which gives an explicit description of the eigenvalue spectrum of the biased random transposition shuffle. We will do this by relating the card shuffle with the representation theory of the symmetric group. We first define some relevant elements in the group algebra which encode the transition matrix. 

\begin{defn}
    For disjoint subsets $S, T \subseteq [N]$, let $\Flip(S)$ be the set of transpositions swapping two elements in $S$ and let $\Flip(S, T)$ be the set of transpositions swapping one element of $S$ with one element in $T$. Define the group algebra elements
    \begin{equation}
        \mathscr{T}_S := \sum_{x \in \Flip(S)} x, \quad \text{ and }\quad \mathscr{T}_{S, T} := \sum_{x \in \Flip(S, T)} x. 
    \end{equation}
    We also define the group algebra element 
    \begin{equation}\label{eqn:defn-of-A}
        \mathscr{A} := \left ( \frac{a^2 |A| + b^2 |B|}{N^2} \right ) \cdot \id + \frac{2a^2}{N^2} \mathscr{T}_A + \frac{2b^2}{N^2} \mathscr{T}_B + \frac{2ab}{N^2} \mathscr{T}_{A, B}.
    \end{equation}
\end{defn}

The proof of \Cref{thm:main-theorem-3} involves diagonalizing the linear operator on $\mathbb{C}[\mathfrak{S}_N]$ given by left multiplication by $\mathscr{A}$. The definition of $\mathscr{A}$ in Equation~\ref{eqn:defn-of-A} exactly encodes the transition probabilities of our card shuffle. Specifically, if we begin with a probability distribution $\pi$ on $\mathfrak{S}_N$, the distribution after one shuffle will be $\mathscr{A}\pi$.  Thus, the eigenvalue spectrum of the transition matrix will be equal to the eigenvalue spectrum of left multiplication by $\mathscr{A}$ on $\mathbb{C}[\mathfrak{S}_N]$. To describe the eigenvalues of our transition matrix, we define $\Eig^\lambda_{\mu, \nu}$ as 
\[
    \Eig^\lambda_{\mu, \nu} := \frac{a^2 |A| + b^2 |B|}{N^2} + \frac{2(a^2 - ab)}{N^2} \Diag(\mu) + \frac{2(b^2 -ab)}{N^2} \Diag(\nu) + \frac{2ab}{N^2} \Diag(\lambda),
\]
for all partitions $\lambda \vdash N$, $\mu \vdash |A|$, and $\nu \vdash |B|$. The following result states that the eigenvalues of $\mathscr{A}$ are exactly $\Eig^\lambda_{\mu, \nu}$ for various triples of partitions $(\lambda, \mu, \nu)$. 

\begin{thm}\label{thm:spectrum-of-A}
    Left multiplication by $\mathscr{A}$ on $\mathbb{C}[\mathfrak{S}_N]$ has eigenvalue spectrum $\Eig^\lambda_{\mu, \nu}$ with multiplicities $f_\lambda f_\mu f_\nu c^\lambda_{\mu, \nu}$ for all $\lambda \vdash N$, $\mu \vdash |A|$, and $\nu \vdash |B|$. 
\end{thm}

\begin{proof}
    From Maschke's theorem, we can decompose the group algebra $\mathbb{C}[\mathfrak{S}_N]$ as $\mathfrak{S}_N$-representations as
    \begin{equation}
        \mathbb{C}[\mathfrak{S}_N] = \bigoplus_{\lambda \vdash N} (S^\lambda)^{\oplus f_\lambda},
    \end{equation}
    where $S^\lambda$ is the Specht module corresponding to the partition $\lambda$. Since subrepresentations are invariant under left multiplication by $\mathscr{A}$, it is enough to diagonalize $\mathscr{A}$ on $S^\lambda$. We can rewrite Equation~\ref{eqn:defn-of-A} as 
    \begin{equation}\label{eqn:A-alt-defn}
        \mathscr{A} = \left ( \frac{a^2 |A| + b^2 |B|}{N^2} \right ) \cdot \id + \frac{2(a^2 - ab)}{N^2} \mathscr{T}_A + \frac{2(b^2 - ab)}{N^2} \mathscr{T}_B + \frac{2ab}{N^2} \mathscr{T}_{A \cup B}.
    \end{equation}
    It is well known (see \cite[Exercise 27.9]{Etingof2024}) that $\mathscr{T}_{[N]}$ acts on $S^\lambda$ for $\lambda \vdash N$ by scalar multiplication by $\Diag(\lambda)$. Since the outer two terms in  Equation~\ref{eqn:A-alt-defn} act by scalar multiplication on $S^\lambda$, it is enough to diagonalize the sum of the inner two terms. To this end, we view $S^\lambda$ as a $\mathfrak{S}_A \times \mathfrak{S}_B$ representation. It follows from the Littlewood--Richardson rule \cite[Proposition 1]{Zelevinsky1981} that  
    \begin{equation}\label{eqn:LR}
        \text{Res}_{\mathfrak{S}_A \times \mathfrak{S}_B}^{\mathfrak{S}_N} S^\lambda = \bigoplus_{\substack{\mu \vdash |A| \\ \nu \vdash |B|}} (S^\mu \boxtimes S^\nu)^{\oplus c^\lambda_{\mu, \nu}}
    \end{equation}
    as $\mathfrak{S}_A \times \mathfrak{S}_B$ modules. The sum of the inner two terms in Equation~\ref{eqn:A-alt-defn} act on each copy of $S^\mu \boxtimes S^\nu$ by scalar multiplication by 
    \begin{equation}
        \frac{2(a^2 - ab)}{N^2} \Diag(\mu) + \frac{2(b^2 - ab)}{N^2} \Diag(\nu). 
    \end{equation}
    Adding the scalar which the sum of the outer two terms in Equation~\ref{eqn:A-alt-defn} act on $S^\lambda$, we get the desired eigenvalue. The multiplicity is given by the fact that $\dim (S^\mu \boxtimes S^\nu) = f_\mu f_\nu$ and $S^\mu \boxtimes S^\nu$ appears $f_\lambda c^\lambda_{\mu, \nu}$ times in $\mathbb{C}[\mathfrak{S}_N]$. This completes the proof to the theorem. 
\end{proof}

\begin{proof}[Proof of \Cref{thm:main-theorem-3}]
    As mentioned in the paragraph after Equation~\ref{eqn:defn-of-A}, the eigenvalue spectrum of the transition matrix is exactly the eigenvalue spectrum of left multiplication of $\mathscr{A}$ on $\mathbb{C}[\mathfrak{S}_N]$. \Cref{thm:main-theorem-3} follows immediately from \Cref{thm:spectrum-of-A}. 
\end{proof}

\section{Lower Bound}
    In this section, we prove the lower bound of \Cref{thm:main-theorem-1}. This will follow from the limiting behavior of the number of fixed points described by \Cref{thm:main-theorem-4'}. 

\subsection{Asymptotics of fixed points}

For the rest of this section, let $V$ be the defining representation of $\mathfrak{S}_N$. For any permutation $\pi \in \mathfrak{S}_N$, let $\Fix(\pi)$ be the number of fixed points of $\pi$. The following lemma gives a representation-theoretic interpretation of the moments of $\Fix(\pi)$ for a random permutation $\pi$. 

\begin{lem}\label{lem:fixed-points}
    Let $\theta : \mathfrak{S}_N \to [0, 1]$ be a probability distribution on $\mathfrak{S}_N$ and let $\vartheta \in \mathbb{C}[\mathfrak{S}_N]$ the corresponding element in the group algebra. 
    \begin{enumerate}[label = (\alph*)]
        \item The expected number of fixed points of a permutation picked according to $\theta$ is the trace of $\vartheta$ on $V$.
        \item The $p\textsuperscript{th}$ moment of the number of fixed points of a permutation picked according to $\theta$ is the trace of $\vartheta$ on $V^{\otimes p}$. 
    \end{enumerate}
\end{lem}

\begin{proof}
    The group algebra element $\vartheta$ is given by $\sum \theta(\pi) \pi \in \mathbb{C}[\mathfrak{S}_N]$ where the sum ranges over all permutations. Viewing $\pi$ as an element of $\End(V)$, the trace $\tr(\pi)$ is equal to the number of fixed points of $\pi$. Thus, we have 
    \begin{equation}
        \tr (\vartheta) = \sum_{\pi \in \fS_N} \theta(\pi) \tr (\pi) = \sum_{\pi \in \fS_N} \theta(\pi) \Fix(\pi) = \mathbb{E}_\theta [\Fix(\pi)]. 
    \end{equation}
    This proves (1). To prove (2), observe that $\Fix(\pi) = \tr(\pi) = \chi_V(\pi)$ where $\chi_V$ is the character of $V$. The character of the tensor product $V^{\otimes p}$ is equal to $\chi_V^p$. Thus, viewing each $\pi$ as an element of $\End(V^{\otimes p})$, we have  
    \begin{equation}
        \tr (\vartheta) = \sum_{\pi \in \fS_N} \theta(\pi) \tr (\pi) = \sum_{\pi \in \fS_N} \theta(\pi) \Fix(\pi)^p = \mathbb{E}_\theta [\Fix(\pi)^p]. 
    \end{equation} 
\end{proof}

To prove \Cref{thm:main-theorem-4'} we also need the following lemma from~\cite[Equation 5.5]{Benkart2016} describing the irreducible subrepresentations of tensor powers of the defining representation. Let $S(p, t)$ denote the \textbf{Stirling number of the second kind}, and let $K_{\lambda, \mu}$ denote the \textbf{Kostka number}. 

\begin{lem}\label{lem:permutation-module-decomposition}
    As $\fS_N$-representations, we have the decomposition
    \[
        V^{\otimes p} = \bigoplus_{\lambda} m^\lambda_p S^\lambda, \quad \text{where} \quad m^\lambda_p := \sum_{t = 0}^N S(p, t) K_{\lambda, (N-t, 1^t)},
    \]
\end{lem}

We are ready for the proof of \Cref{thm:main-theorem-4'}.

\begin{proof}[Proof of \Cref{thm:main-theorem-4'}]
    Since the Poisson distribution is determined by its moments \cite[Example 6.3]{DasGupta2008}, it is enough to show that the $p\textsuperscript{th}$ moment of $\Fix_c$ converges to the $p\textsuperscript{th}$ moment of a $\Poiss(1 + e^c/2)$ random variable. From \Cref{lem:fixed-points}, the $p$th moment of $\Fix_c$ is exactly the trace of $\mathscr{A}^K$ on $V^{\otimes p}$. From \Cref{lem:permutation-module-decomposition}, Equation~\ref{eqn:LR}, and \Cref{thm:spectrum-of-A}, we have
    \begin{align}
        \tr \left ( \mathscr{A}^K \right ) & = \sum_{\lambda \vdash N} \sum_{\mu, \nu \vdash n} m^\lambda_p c^\lambda_{\mu, \nu} f^\mu f^\nu (\Eig^\lambda_{\mu, \nu})^K \label{eqn:trace}\\ & = \sum_{j = 0}^p \sum_{\substack{\lambda \vdash N \\ \lambda_1 = N-j}}   m^\lambda_p \left \{ \sum_{\mu, \nu \vdash n} c^\lambda_{\mu, \nu} f^\mu f^\nu (\Eig^\lambda_{\mu, \nu})^K \right \}.
    \end{align}
    Since we are fixing $p$ and letting $N$ tend to infinity, there are only finitely many partitions (depending on $p$) which appear in the sum. These partitions are of the form $\lambda = (N-j, T)$ where $0 \leq j \leq p$, and $T$ is a partition of $j$. Take any partition $\lambda = (N-j, T)$ of this form. We first compute the asymptotics of  
    \begin{equation}\label{eqn:focus-asymptotics-here}
        \sum_{\mu, \nu \vdash n} c^\lambda_{\mu, \nu} f^\mu f^\nu (\Eig^\lambda_{\mu, \nu})^K. 
    \end{equation}
    Suppose that $\mu, \nu \vdash n$ satisfy $c^\lambda_{\mu, \nu} > 0$. Then, \cite[Lemma 2.52]{preprint} implies that they must be of the form 
    \[
        \mu = (n-i_1, T_1), \quad \nu = (n-i_2, T_2), \quad i_1 + i_2 \leq j, \quad T_1 \vdash i_1, T_2 \vdash i_2.
    \]
    In particular, the number of non-zero summands in Equation~\ref{eqn:focus-asymptotics-here} is bounded above by a constant depending only on $p$. From \cite[Lemma 2.25]{preprint}, we have the asymptotics
    \[
        \Eig^\lambda_{\mu, \nu} = 1 - \frac{B_{i_1, i_2, j}}{N} + O \left ( \frac{1}{N^2} \right )
    \]
    where  $B_{i_1, i_2, j} := i_1 a^2 + i_2 b^2 + (2j - i_1 - i_2)ab$. Using the approximation $1 - x = e^{-x} + O(x^2)$, the contribution of all copies of $S^\mu \boxtimes S^\nu$ in $S^\lambda$ to the trace is 
    \begin{align}
        c^\lambda_{\mu, \nu} f_\mu f_\nu (\Eig^\lambda_{\mu, \nu})^K & = \frac{N^{i_1 + i_2}}{2^{i_1 + i_2} (i_1)! (i_2)!} f_{T_1} f_{T_2} c^\lambda_{\mu, \nu} \cdot \frac{e^{\frac{B_{i_1, i_2, j}}{2b} c}}{N^{\frac{B_{i_1, i_2, j}}{2b}}} + o(1)\label{eqn:contribution} \\
        & = C \cdot N^{\frac{2b (i_1 + i_2) - B_{i_1, i_2, j}}{2b}} + o(1)\label{eqn:order-of-growth} \\
        & = C \cdot N^{E_{i_1, i_2, j}} + o(1),
    \end{align}
    where we define $E_{i_1, i_2, j} := \frac{2b(i_1 + i_2) - B_{i_1, i_2, j}}{2b}$. In Equation~\ref{eqn:order-of-growth} we consolidated all constants which are of constant order with respect to $N$ in the constant $C$. 
    
    We study the maximum value of $E_{i_1, i_2, j}$ depending on the values of $i_1, i_2, j$. The following lemma implies that $E_{i_1, i_2, j}$ is will less than or equal to $0$, and it will be equal to zero for a single choice of the pair $(i_1, i_2)$.
    
    \begin{lem}\label{lem:computing-exponent} Let $a > b$. 
        \begin{enumerate}[label = (\alph*)]
            \item We have $E_{i_1, i_2, j} \leq 0$. If $E_{i_1, i_2, j} = 0$, then $i_1 = 0$, $i_2 = j$, and $B_{i_1, i_2, j} = 2jb$. 
            \item Let $i_1 = 0$ and $i_2 = j$. Then $c^\lambda_{\mu, \nu} > 0$ if and only if $\mu = (n)$ and $\nu = (n-j, T)$. If this happens, then $c^{\lambda}_{\mu, \nu} = 1$.
        \end{enumerate}
    \end{lem}
    
    From \Cref{lem:computing-exponent}, the asymptotics of Equation~\ref{eqn:focus-asymptotics-here} for any partition $\lambda = (N-j, T)$ are given by  
    \[
        \sum_{\mu, \nu \vdash n} c^\lambda_{\mu, \nu} f_\mu f_\nu \left (\Eig^\lambda_{\mu, \nu} \right )^K = \frac{f_T}{j!} \left ( \frac{e^c}{2} \right )^j + o(1).
    \]
    From Equation~\ref{eqn:trace}, we have 
    \begin{align}
        \tr \left ( \mathscr{A}^K \right ) & = o(1) + \sum_{j = 0}^p \sum_{T \vdash j} \frac{f_T}{j!} \left ( \frac{e^c}{2} \right )^j \sum_{t = j}^p S(p, t) \binom{t}{j} f_T\label{eqn:hi} \\
        & = o(1) + \sum_{t = 0}^p S(p, t) \sum_{j = 0}^t \binom{t}{j} \left ( \frac{e^c}{2} \right )^j \left [ \frac{\sum_{T \vdash j} f_T^2}{j!} \right ] \\
        & = o(1) + \sum_{t = 0}^p S(p, t) \left (1  + \frac{e^c}{2} \right )^t.\label{eqn:finally!}
    \end{align}
    From~\cite[Equation 1.3-14]{Haight1967}, the right hand side of Equation~\ref{eqn:finally!} is exactly the $p\textsuperscript{th}$ moment of a Poisson random variable of rate $1 + \frac{e^c}{2}$. This suffices for the proof. 
\end{proof} 

\begin{remark}
    In \Cref{thm:main-theorem-4'}, it is important that $b < a$. Indeed, the condition that $b < a$ plays an important role in limiting the sources that contribute to the trace of $\mathscr{A}^K$. In contrast, in the case $a = b = 1$ corresponding to the random transposition shuffle, it is shown in~\cite[Equation 1.6]{Matthews1988} that
\begin{equation}\label{eqn:matthews-fix-limit}
    \Fix_c \xrightarrow{\text{dist}} \Poiss \left (1 + e^c \right ).
\end{equation}
This illustrates the clear difference between the $a < b$ case and the $a = b = 1$ case.
\end{remark}

\subsection{Proof of lower bound}

We can now prove the lower bound of \Cref{thm:main-theorem-1} by comparing the distribution of our shuffle to the distribution of its fixed points. 

\begin{proof}[Proof of lower bound of \Cref{thm:main-theorem-1}]
    For $0 \leq k \leq N$, let $\fS_N^{(k)}$ be the subset of permutations with exactly $k$ fixed points. Then we have 
    \begin{align*}
        d_{\TV}(U, P^t(\id, \cdot)) & = \frac{1}{2} \sum_{k = 0}^N \sum_{\pi \in \fS_N^{(k)}} |U(\pi) - P^t(\id, \pi)| \\
        & \geq \frac{1}{2} \sum_{k = 0}^N \left |U(\fS_N^{(k)}) - P^t(\id, \fS_N^{(k)}) \right | \\
        & = d_{\TV}(\Fix, \Fix_c) \\
        & = d_{\TV} \left (\Poiss(1), \Poiss \left ( 1 + \frac{e^c}{2} \right ) \right ) + o(1),
    \end{align*}
    where the last equality follows from \Cref{thm:main-theorem-4'} and the classical \textit{problème des rencontres}. The lower bound follows from~\cite[p.\ 44]{LeCam2000} giving
    \begin{equation}
        d_{\TV} \left ( \Poiss(1), \Poiss \left ( 1 + \frac{e^c}{2} \right ) \right ) \geq H^2 \left (\Poiss(1), \Poiss \left ( 1 + \frac{e^c}{2} \right ) \right ),
    \end{equation}
    where $H^2$ is the \textbf{(squared) Hellinger distance}. The right hand side of the lower bound of \Cref{thm:main-theorem-1} is an explicit computation of the Hellinger distance between two Poisson random variables. 
\end{proof}

\section{Upper Bound}

In this section, we make a few comments on the upper bound of \Cref{thm:main-theorem-1}. From~\cite[Lemma 12.18(ii)]{LPW-MCMT} along with \Cref{thm:main-theorem-3}, we get the following upper bound. 

\begin{lem}\label{lem:l2-bound}
    Let $|A| = |B| = n$ and $N = 2n$. Let $U$ be the uniform distribution on $\fS_N$. Then, any time $t \geq 0$, we have the bound 
    \begin{equation}\label{eqn:l2-bound}
        d_{\TV} (P^t(x, \cdot), U)^2 \leq \frac{1}{4} \sum_{\substack{\lambda \vdash N \\ \lambda \neq (N)}} \sum_{\lambda : c^\lambda_{\mu, \nu} > 0} c^\lambda_{\mu, \nu} f_\lambda f_\mu f_\nu \cdot |\Eig^\lambda_{\mu, \nu}|^{2t}.
    \end{equation}
\end{lem}

We prove the upper bound in \Cref{thm:main-theorem-1} by splitting up the sum in Equation~\ref{eqn:l2-bound} into several zones based on the indexing partition. Approximately, we split up the space of partitions of $N$ into approximately three zones. These zones are as follows: 
\begin{defn}
    Let $a^* := 2-a^{-1}$. We define the \textbf{Red}, \textbf{Blue}, and \textbf{Yellow} zones explicitly by 
    \begin{align*}
        \Zone_R & := \{\lambda : \lambda_1, \lambda_1^* \leq n \}, \\
        \Zone_B & := \{ \lambda : n \leq \lambda_1 \leq a^*n, \lambda_1^* \leq n\} \cup \{\lambda : n \leq \lambda_1^* \leq a^*n, \lambda_1 \leq n \}, \\
        \Zone_Y & := \{\lambda : 2n-1 \geq \lambda_1 \geq a^* n \} \cup \{ \lambda : \lambda_1^* \geq a^*n \}. 
    \end{align*}
\end{defn}

Diagrammatically, these zones are depicted in \Cref{fig:zones-skeleton} where the space of partitions is represented as a two-dimensional plane where the $x$-axis corresponds to the length of the first row and the $y$-axis corresponds to the length of the first column. In the analysis, we also partition each zone into several subzones. 

\begin{figure}[ht]
    \begin{center}
    \begin{tikzpicture}[scale = 1.2]
        \definecolor{lightblue}{rgb}{0.68, 0.85, 0.90}

        \draw[->, line width=0.25mm] (0,0) -- (4.4,0) node[right] {$\lambda_1$};
        \draw[->, line width=0.25mm] (0,0) -- (0,4.4) node[right] {$\lambda_1^*$};

        \draw[fill = red, opacity=0.5] (0, 0) -- (2, 0) -- (2, 2) -- (0, 2) -- cycle;
        \draw[line width=0.25mm] (0, 0) -- (2, 0) -- (2, 2) -- (0, 2) -- cycle;

        \draw[fill = lightblue] (0, 2) -- (2, 2) -- (1.2, 2.8) -- (0, 2.8) -- cycle;
        \draw[line width=0.25mm] (0, 2) -- (2, 2) -- (1.2, 2.8) -- (0, 2.8) -- cycle;

        \draw[fill = lightblue] (2, 0) -- (2, 2) -- (2.8,1.2) -- (2.8,0) -- cycle;
        \draw[line width=0.25mm] (2, 0) -- (2, 2) -- (2.8,1.2) -- (2.8,0) -- cycle;

        \draw[fill = yellow, opacity=0.5] (2.8, 0) -- (2.8, 1.2) -- (4, 0) -- cycle;
        \draw[line width=0.25mm] (2.8, 0) -- (2.8, 1.2) -- (4, 0) -- cycle;

        \draw[fill = yellow, opacity=0.5] (0, 2.8) -- (1.2, 2.8) -- (0, 4) -- cycle;
        \draw[line width=0.25mm] (0, 2.8) -- (1.2, 2.8) -- (0, 4) -- cycle;

        \draw[line width=0.25mm] (0,0) -- (0,4) -- (4,0) -- cycle;

        \draw (0,0) -- (2,0) node[below] {$n$} -- (2.8,0) node[below] {$a^*n$} -- (4,0) node[below] {$2n$};
        \draw (0,0) -- (0,2) node[left] {$n$} -- (0,2.8) node[left] {$a^*n$} -- (0,4) node[left] {$2n$};

        \draw (3, 3) node[right] {$a^* := 2-a^{-1}$};

        \draw (1, 0.65) node[above] {\Huge $R$};
        \draw (2.4, 0.5) node[above] {\Large $B$};
        \draw (0.5, 2.4) node[right] {\Large $B$};
        \draw (3.2, 0.1) node[above] {$Y$};
        \draw (0.1, 3.2) node[right] {$Y$};
    \end{tikzpicture}
    \end{center}
    \caption{Cartesian plane with $x$-axis $\lambda_1$ and $y$-axis $\lambda_1^*$}\label{fig:zones-skeleton}
\end{figure}

Over each sub-zone, we bound the maximum value of $\Eig^\lambda_{\mu, \nu}$ and the dimension of $c^\lambda_{\mu, \nu} f_\lambda f_\mu f_\nu$ depending on the length of the first row and first column. The main terms in the sum come from partitions with long first row. To show that the contribution coming from the other partitions is negligible, we need a good understanding of when $c^\lambda_{\mu, \nu} > 0$. Equivalently, we need to understand the triples $(\lambda, \mu, \nu)$ which appear non-trivially in Equation~\ref{eqn:l2-bound}. To do this, we rely on the theory of hives~\cite{Knutson1999} and more generally the representation theory of semisimple Lie algebras. 

\begin{remark}
    For random transpositions, Diaconis and Shahshahani use zones similar to \Cref{fig:zones-skeleton}. However, in the biased case, the analysis is considerably more delicate and we need to divide the red, blue, and yellow zones into \textit{additional} sub-zones. Some of these sub-zones then need to be divided into even smaller sub-zones, where these sub-zones are determined \textit{dynamically}. For more details of this analysis, we direct the reader to the preprint~\cite{preprint}. 
\end{remark}


\acknowledgements{The authors thank Ezra Edelman for introducing us to the Hellinger distance. The authors thank Lauren Williams for helpful comments on the extended abstract. The authors also thank Johnny Gao, Laura Colmenarejo, and Grant Barkley for enlightening conversations about Littlewood--Richardson coefficients and the hive model. Finally, the authors thank the anonymous reviewers for their helpful comments.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
