# Mixing times of one-sided $k$-transposition shuffles

Evita Nestoridi∗ Kenny Peng∗

###### Abstract

We study mixing times of the one-sided $k$-transposition shuffle. We prove
that this shuffle mixes relatively slowly, even for $k$ big. Using the recent
“lifting eigenvectors” technique of Dieker and Saliola [1] and applying the
$\ell^{2}$ bound, we prove different mixing behaviors and explore the
occurrence of cutoff depending on $k$.

##  1 Introduction

Diagonalizing the transition matrix of a reversible Markov chain is extremely
powerful when wanting to prove that the Markov chain exhibits the cutoff
phenomenon. The first technique for diagonalizing the transition matrix of a
random walk on the Caley graph of a finite group $G$ was introduced by
Diaconis and Shahshahani [2]. The technique, which relies on Schur’s lemma,
requires understanding of the representation and character theory of $G$, and
has been applied for many random walks on groups [3, 4, 5, 6, 7].

Cases where the generating set is not a conjugacy class are much more
challenging. An early example is the case of star transpositions, which was
diagonalized by Flatto, Odlyzko and Wales [8]. Diaconis [9] analyzed this
diagonalization to show cutoff at $n\log n$. In a recent breakthrough, Dieker
and Saliola [1] introduced a new technique to diagonalize the random-to-random
shuffle. The proof of cutoff for random-to-random was completed by Bernstein
and the first author’s eigenvalue analysis [10] and Subag’s lower bound
analysis [11].

Another development was studying the one-sided transposition shuffle on $n$
cards, during which different transpositions are assigned different weights.
Bate, Connor and Matheau–Raven [12] diagonalized this shuffle and proved that
it exhibits cutoff at $n\log n$. One step of this shuffle consists of choosing
a position $R$ uniformly at random, choosing a position $L$ from
$\\{1,2,\cdots,R\\}$ uniformly at random, and then performing the
transposition $(RL)$. Here, we introduce a generalization called the one-sided
$k-$transposition shuffle. As before, we choose a position $R$ uniformly at
random, except now, we pick $k$ positions $L_{1},\cdots,L_{k}$ (not
necessarily distinct) uniformly at random from $\\{1,2,\cdots,R\\},$ and
perform the permutation $(RL_{k})(RL_{k-1})\cdots(RL_{1}).$ These products can
give rise to many types of permutations of varying weights.

Let $P_{n,k}$ denote the transition matrix of the one-sided $k-$transposition
shuffle on $n$ cards and let $U$ denote the uniform measure on $S_{n}$. We
define the total variation- and $\ell^{2}$\- distance between $P_{n,k}$ and
$U$ as follows:

$d^{(n,k)}(t):=\left\lVert
P_{n,k}^{t}-U\right\rVert_{\operatorname{T.V.}}=\bigg{\\{}\frac{1}{2}\sum_{y\in
S_{n}}|P_{n,k}^{t}(id,y)-U(y)|\bigg{\\}}\mbox{ and
}\left\lVert\frac{P_{n,k}^{t}}{U}-1\right\rVert_{2}^{2}:=\left(\sum_{y\in
S_{n}}\left|\frac{P_{n,k}^{t}(id,y)}{U(y)}\right|-1\right),$

where $P_{n,k}^{t}(x,y)$ is the probability of moving from $x$ to $y$ after
$t$ steps of the shuffle. We note that since $P_{n,k}$ is transitive, we can
without loss of generality start the card shuffle at the identity element $id$
of $S_{N}$. The mixing time of $P_{n,k}$ is defined as

$t_{\textup{mix}}(\varepsilon)=\min\\{t:d^{(n,k)}(t)\leq\varepsilon\\}.$

A shuffle exhibits cutoff if as $n$ grows, the total variation distance is
almost equal to one and then suddenly drops and approaches zero. More
formally, $P_{n,k}$ is said to exhibit cutoff at time $t_{n,k}$ with window
$w_{n,k}=o(t_{n,k})$ if and only if

$\lim_{c\rightarrow\infty}\lim_{n\rightarrow\infty}d^{(n,k)}(t_{n,k}-cw_{n,k})=1\quad\mbox{and}\quad\lim_{c\rightarrow\infty}\lim_{n\rightarrow\infty}d^{(n,k)}(t_{n,k}+cw_{n,k})=0.$

We may analogously define the $\ell^{2}$-cutoff. Salez [13] gives breakthrough
developments and a nice exposition on the history of cutoff. In this paper, we
present a series of results involving the mixing time of $P_{n,k}$ for
different regimes of $k$:

  * R1.

When $k=n^{o(1)}$, $P_{n,k}$ exhibits total-variation cutoff at $t=n\log n.$

  * R2.

When $k=n^{\gamma}$ for $\gamma\in(0,1]$, we have $(1-\gamma)n\log n\leq
t_{\textup{mix}}(1/2)\leq(1-\frac{\gamma}{2})n\log n$ with $\ell^{2}$ cutoff
at $t=(1-\frac{\gamma}{2})n\log n.$

  * R3.

When $k=\Omega(n\log n)$, $P_{n,k}$ mixes in order $n$ steps without cutoff.

In particular, we observe the surprising fact that even as $k$ increases
initially, the mixing time does not change. This stands in sharp contrast to
other classes of shuffles, such as the $k-$cycle shuffle [3, 14], and the
conjugacy class random walks [4]. In fact, this turns out to be a very slow
shuffle even when $k$ is very big (e.g., when $k=n\log n$). This is unlike
other non-local shuffles such as the riffle shuffles, which Bayer and Diaconis
proved mixes in $\frac{3}{2}\log_{2}n$ steps [15].

####

We now define the shuffle more carefully.

######  Definition 1 (One-sided $k-$transposition shuffle).

The one-sided $k-$transposition shuffle $P_{n,k}$ is the ergodic random walk
on $S_{n}$ generated by the following probability distribution:

$P_{n,k}(\tau)=\begin{cases}\frac{1}{nj^{k}},&\qquad\text{if
}\tau=(j;i_{1},\cdots,i_{k})\text{ for }1\leq i_{1},\cdots,i_{k}\leq j\leq
n\\\ 0,&\qquad\text{otherwise,}\end{cases}$

where we set the notation

$(j;i_{1},\cdots,i_{k}):=(ji_{k})\cdots(ji_{1}),$

the composition of $k$ transpositions with a common element.

Our strategy is to calculate the eigenvalues of $P_{n,k}$ using the lifting
eigenvectors method. This technique, pioneered by Dieker and Saliola [1],
allows us to compute the eigenvalues of the $P_{n+1,k}$ from the $P_{n,k}$.

Once we diagonalize $P_{n,k}$, we will leverage the following classical bound,
which connects the eigenvalues
$1=\beta_{1}>\beta_{2}\geq\cdots\geq\beta_{n!}>-1$ of $P_{n,k}$ to its total
variation distance from the stationary distribution:

$4\left\lVert
P_{n,k}^{t}-U\right\rVert_{\operatorname{T.V.}}^{2}\leq\sum_{i\neq
1}\beta_{i}^{2t}=\left\lVert\frac{P_{n,k}^{t}}{U}-1\right\rVert_{2}^{2}.$ (1)

We now state our main results. The first result discusses a general upper
bound for the mixing time, which turns out to be sharp for $k=n^{o(1)}$. We
also provide a better bound for the case $k=n^{\gamma}$ with $\gamma\in(0,1]$,
which turns out to be sharp for the $\ell^{2}$ norm.

######  Theorem 2 (Upper bounds on total variation and $\ell^{2}$ distance).

  1. (i)

For $k\geq 1$, when $t=n\log n+cn$ for $n$ sufficiently large, there exists a
universal constant $A$ such that

$4\left\lVert
P_{n,k}^{t}-U\right\rVert_{\operatorname{T.V.}}^{2}\leq\left\lVert\frac{P_{n,k}^{t}}{U}-1\right\rVert_{2}^{2}<Ae^{-c}.$

  2. (ii)

For $k=n^{\gamma}$ with $\gamma\in(0,1]$, when $t=(1-\frac{\gamma}{2})n\log
n+cn$ and $c>3$ for $n$ sufficiently large,

$4\left\lVert
P_{n,k}^{t}-U\right\rVert_{\operatorname{T.V.}}^{2}\leq\left\lVert\frac{P_{n,k}^{t}}{U}-1\right\rVert_{2}^{2}<10e^{-c}.$

The following theorem discusses the $\ell^{2}$ mixing time, which in
combination with the previous theorem shows (R2).

######  Theorem 3 (Lower bounds on $\ell^{2}$ distance).

  1. (i)

For $k\geq 1$, when $t=\frac{1}{2}n\log n-cn,$

$\left\lVert\frac{P_{n,k}^{t}}{U}-1\right\rVert_{2}>e^{c}.$

  2. (ii)

For $k=n^{\gamma}$ with $\gamma\in(0,1],$ when $t=(1-\frac{\gamma}{2})n\log
n-\frac{1}{2}n\log\log n-cn,$

$\left\lVert\frac{P_{n,k}^{t}}{U}-1\right\rVert_{2}>e^{c}.$

The next theorem discusses a lower bound on the total variation distance. In
combination with Theorem 2, it concludes cutoff for the the case $k=n^{o(1)}$
as described in (R1).

######  Theorem 4 (Lower bound on total variation distance).

For $k=o\left(\frac{n}{\log n}\right)$, when $t=n\log(n/k)-n\log\log n-cn,$

$\liminf_{n\rightarrow\infty}\left\lVert
P_{k,n}^{t}-U\right\rVert_{\operatorname{T.V.}}\geq
1-\frac{\pi^{2}}{6(c-4)^{2}}.$

The following theorem discusses mixing times for the case where $k$ is big,
giving the results in (R3).

######  Theorem 5 (Mixing time for especially big $k$).

For $k=\Omega(n\log n)$, we have
$t_{\text{mix}}(\varepsilon)=\Theta_{\varepsilon}(n)$. For $k\in[n,n\log n]$,
we have that $t_{\text{mix}}(\varepsilon)=O_{\varepsilon}\left(\frac{n^{2}\log
n}{k}\right)$. We also have that $t_{\text{mix}}(\varepsilon)=\Omega(n)$ for
every $k\geq 1$.

We now outline the remainder of the paper. In Section 2, we give the
definitions needed to describe the spectrum of $P_{n,k}$. In Section 3, we
present the eigenvalues of $P_{n,k}$ and some appropriate bounds. Section 4
contains the proof of Theorem 2(i). Theorem 2(ii) is proven is Section 5. In
Section 6, we present the $\ell^{2}$ lower bounds summarized in Theorem 3. The
total variation bound of Theorem 4 can be found in Section 7. Theorem 5 is
proved in Section 8.

We conclude our introduction by suggesting a few interesting open questions.
We first suggest the question of if there is total-variation cutoff in (R2)
and whether it coincides with the $\ell^{2}$-cutoff.

Another natural question to ask concerns the limit profile of the shuffle. The
limit profile (if it exists) is defined as the function

$\Phi(c)=\lim_{n\rightarrow\infty}d^{(n,k)}(t_{n,k}+cw_{n,k}),$

where $c\in\mathbb{R}$ and $t_{n,k},w_{n,k}$ are the cutoff time of the Markov
chain and the corresponding window. There are a few examples of famous Markov
chains whose limit profile has been determined [15, 16, 17]. Recently, there
has been exciting progress on developing techniques to determine limit
profiles [18, 19, 20], which work well for conjugacy class invariant random
walks or random walks where we have knowledge of the eigenvalues and the
eigenvectors of the transition matrix. It would be very interesting to
determine the limit profile of $P_{n,k}$ for $k=n^{o(1)}$, or simply $k=1$,
since it cannot be studied by the already existing techniques and could lead
to developing new ones.

##  2 Preliminaries: Partitions and Standard Young Tableaux

In this section, we introduce several standard definitions involving
partitions and standard Young tableaux. A partition $\lambda$ of an integer
$n$ is a tuple $(\lambda_{1},\cdots,\lambda_{r})$ of positive integers summing
to $n$ such that $\lambda_{1}\geq\cdots\geq\lambda_{r}.$ We will write
$\lambda\vdash n$ to indicate that $\lambda$ is a partition of $n$, and let
$l(\lambda):=r$ denote the length of $\lambda$, i.e. the number of parts of
$\lambda$.

We may associate a partition $\lambda$ to its Young diagram, which has
$l(\lambda)$ rows of left-aligned boxes, such that from top to bottom the rows
have $\lambda_{1},\lambda_{2},\cdots,\lambda_{r}$ boxes. For example, the
partition $(6,4,2)\vdash 12$ corresponds to the following Young diagram:

$\ydiagram{6,4,2}$

We will often refer to a partition $\lambda$ and its diagram interchangeably.
For example, for partitions $\lambda,\mu\vdash n,$ we write that
$\lambda\trianglerighteq\mu$ (“$\lambda$ dominates $\mu$”) if $\mu$ can be
obtained by moving boxes in $\lambda$ down and to the left.

Given $\lambda\vdash n,$ we can create a standard Young tableau of shape
$\lambda$ by placing each of the numbers $1,2,\cdots,n$ in the diagram of
$\lambda$ such that the numbers are strictly increasing across each row and
down each column. For example, the following is a standard Young tableau of
shape $(6,4,2)\vdash 12:$

$\ytableaushort{123567,489{10},{11}{12}}$

For a standard Young tableau $T$, we let $T(i,j)$ denote the number in the
$i-$th row and $j-$th column. For $T$ given above, $T(2,1)=4.$

For $\lambda\vdash n,$ we denote $\operatorname{SYT}(\lambda)$ as the set of
all standard Young tableaux of shape $\lambda.$ We let
$d_{\lambda}:=|\operatorname{SYT}(\lambda)|$ indicate the dimension of
$\lambda$. Calculating $d_{\lambda}$ is challenging in general, and is given
by the famous hook-length formula. For our purposes, the following bound—which
we will recall later on—suffices.

######  Proposition 6 (Corollary 2 in [2]).

Let $\lambda_{1}$ denote the first part of a partition $\lambda\vdash n$. Then

$\sum_{\begin{subarray}{c}\lambda\vdash n\\\
\lambda_{1}=n-m\end{subarray}}d_{\lambda}^{2}<\frac{n^{2m}}{m!}.$

As we will see in the next section, the standard Young tableaux index the
eigenvalues of the one-sided $k-$transposition shuffle, thus playing an
essential role in our analysis.

##  3 Eigenvalue analysis

In this section, we analyze the eigenvalues of the one-sided $k-$transposition
shuffle, giving bounds that will help obtain results about the shuffle’s
mixing time in several regimes. The following result shows that these
eigenvalues are indexed by standard Young tableaux. We defer the proof, which
uses tools from representation theory, to the appendix.

######  Theorem 7.

The eigenvalues of $P_{n,k}$ are labeled by standard Young tableaux of size
$n$, and the eigenvalue $\operatorname{eig}(T)$ corresponding to a standard
Young tableau $T$ of shape $\lambda$ appears $d_{\lambda}$ times.

Applying (1), this reveals the following bound, which is central to our
analysis.

$4\left\lVert
P_{n,k}^{t}-U\right\rVert_{\operatorname{T.V.}}^{2}\leq\sum_{\begin{subarray}{c}\lambda\vdash
n\\\ \lambda\neq(n)\end{subarray}}d_{\lambda}\sum_{\lambda\in
SYT(\lambda)}\operatorname{eig}(T)^{2t}=\left\lVert\frac{P_{n,k}^{t}}{U}-1\right\rVert_{2}^{2},$
(2)

In the following section, we provide the necessary definitions to give a
formula for $\operatorname{eig}(T).$

###  3.1 A formula for $\operatorname{eig}(T)$

In this section, we provide a formula for the eigenvalues of $P_{n,k}$, which
we use to prove a series of results about the shuffle’s mixing time. We begin
by stating this formula. We defer the proof, which uses tools from
representation theory, to the appendix.

Any standard Young tableau $T\in\operatorname{SYT}(\lambda)$ may be identified
with a series of partitions

$\emptyset=\lambda^{(0)},\lambda^{(1)},\cdots,\lambda^{(n)}=\lambda,$ (3)

where $\lambda^{(i+1)}$ is obtained from $\lambda^{(i)}$ by adding one box to
row $a^{(i)}$. Here, $\lambda^{(i)}$ is the partition obtained by looking at
the boxes of $\lambda$ containing the integers $1$ through $i$, so the number
of boxes of $\lambda^{(i)}$ is $|\lambda^{(i)}|=i.$ Then the eigenvalue
corresponding to $T$ can be described through functions
$\nu(\lambda^{(i)},a^{(i)}),$ which we now work to define.

######  Definition 8.

For $a\geq 1,$ let

$S_{\ell}(a):=\\{(a,x_{1},\cdots,x_{\ell})\in\mathbb{N}^{\ell+1}:a\geq
x_{1}\geq\cdots\geq x_{\ell}\geq 1\\}.$

Then for $\tilde{\bm{a}}\in S_{\ell}(a)$ and $i\in\mathbb{N},$

$\displaystyle u(\tilde{\bm{a}})$ $\displaystyle:=\text{the number of distinct
elements in }\tilde{\bm{a}}\text{ not equal to }a$ $\displaystyle
d_{i}(\tilde{\bm{a}})$ $\displaystyle:=\max\\{0,\text{one fewer than the
number of occurrences of }i\text{ in }\tilde{\bm{a}}\\}.$

Then using the definitions above, we can define the following important set of
functions. Let $p<n$. For a partition $\pi\vdash p$ and $a\in[\ell(\pi)+1],$

$\nu(\pi,a):=\frac{1}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\sum_{\tilde{\bm{a}}\in
S_{\ell}(a)}(-1)^{u(\tilde{\bm{a}})}\prod_{1\leq i\leq
a}\pi_{i}^{d_{i}(\tilde{\bm{a}})}.$ (4)

(Here, we use the convention that $0^{0}=1.$) The following result, which we
prove in the appendix, shows how these functions yield the eigenvalues of our
shuffle.

######  Theorem 9.

For $T\in\operatorname{SYT}(\lambda)$ identified with
$\lambda^{(0)},\lambda^{(1)},\cdots,\lambda^{(n)}$ (as above), the eigenvalue
corresponding to $T$ is given by

$\operatorname{eig}(T)=\frac{1}{n}\sum_{i=0}^{n-1}\nu(\lambda^{(i)},a^{(i)}),$

where we recall that $\lambda^{(i+1)}$ is obtained by adding one box in row
$a^{(i)}$ to $\lambda^{(i)}$.

###  3.2 Bounding eigenvalues

To make use of the formula we have for the eigenvalues of $P_{n,k}$, further
analysis of $\nu(\pi,a)$ is required. The following decomposition will be
useful:

######  Definition 10.

For a partition $\pi\vdash p,$ and $a\in[\ell(\pi)+1]$ and $u\geq 0$, define

$\nu(\pi,a,u):=\frac{(-1)^{u}}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\sum_{\begin{subarray}{c}\tilde{\bm{a}}\in S_{\ell}(a)\\\
u(\tilde{\bm{a}})=u\end{subarray}}\prod_{1\leq i\leq
a}\pi_{i}^{d_{i}(\tilde{\bm{a}})},$ (5)

so that

$\nu(\pi,a)=\sum_{u=0}^{k}\nu(\pi,a,u).$

The following lemma says the we only need to study $\nu(\pi,a,u)$ for $u<a$.

######  Proposition 11.

For a partition $\pi\vdash p$, $a\in[\ell(\pi)+1],$ and $u\geq a,$ we have
$\nu(\pi,a,u)=0.$

###### Proof.

Since $u(\tilde{\bm{a}})<a\leq u$ when $\tilde{\bm{a}}\in S_{\ell}(a),$ there
are no terms in the last summation in (5). ∎

The functions $\nu(\pi,a,u)$ are individually much easier to understand than
their sum, $\nu(\pi,a)$. In particular, view $\nu(\pi,a,u)$ as a polynomial in
$\pi_{1},\pi_{2},\cdots$. Then because $u(\tilde{\bm{a}})=u$ is fixed, all
terms of this polynomial have the same sign $(-1)^{u}.$ Moreover, each term of
the polynomial has the same degree $\sum_{1\leq i\leq
a}d_{i}(\tilde{\bm{a}})=\ell-u$. We leverage these observations in the
following results.

######  Proposition 12.

For a partition $\pi\vdash p$, $a\in[\ell(\pi)+1],$ and $a>u,$

$|\nu(\pi,a,u)|\leq|\pi|^{-u}$

and

$\nu(\pi,a,u)\begin{cases}\leq 0&\text{if }u\text{ is odd}\\\ \geq 0&\text{if
}u\text{ is even}\end{cases}.$

###### Proof.

To find the sign, note that $\pi_{i}\geq 0$ for all $i$. To bound the absolute
value, note that

$\displaystyle|\nu(\pi,a,u)|$
$\displaystyle=\left|\frac{(-1)^{u}}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\sum_{\begin{subarray}{c}\tilde{\bm{a}}\in S_{\ell}(a)\\\
u(\tilde{\bm{a}})=u\end{subarray}}\prod_{1\leq i\leq
a}\pi_{i}^{d_{i}(\tilde{\bm{a}})}\right|$
$\displaystyle\leq\frac{1}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}(\pi_{1}+\cdots+\pi_{a})^{\ell-u},$

where we used that each term in $\sum_{\begin{subarray}{c}\tilde{\bm{a}}\in
S_{\ell}(a)\\\ u(\tilde{\bm{a}})=u\end{subarray}}\prod_{1\leq i\leq
a}\pi_{i}^{d_{i}(\tilde{\bm{a}})}$ is a distinct monomial of degree $\ell-u.$
Finally,

$\displaystyle\frac{1}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}(\pi_{1}+\cdots+\pi_{a})^{\ell-u}$
$\displaystyle\leq\frac{1}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}|\pi|^{\ell-u}=|\pi|^{-u},$

as desired. ∎

For our purposes, this bound is sufficient for $u\geq 1,$ but for $u=0,$ we
require a sharper bound. It turns out that the exact value is simple:

######  Proposition 13.

For a partition $\pi\vdash p$ and $a\in[\ell(\pi)+1],$ we have
$\nu(\pi,a,0)=\left(\frac{\pi_{a}+1}{|\pi|+1}\right)^{k}.$

###### Proof.

For $\tilde{\bm{a}}\in S_{\ell}(a),$ $u(\tilde{\bm{a}})=0$ if and only if
$\tilde{\bm{a}}=(a,a,\cdots,a).$ Thus,

$\displaystyle\nu(\pi,a,0)$
$\displaystyle=\frac{(-1)^{u}}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\sum_{\begin{subarray}{c}\tilde{\bm{a}}\in S_{\ell}(a)\\\
u(\tilde{\bm{a}})=0\end{subarray}}\prod_{1\leq i\leq
a}\pi_{i}^{d_{i}(\tilde{\bm{a}})}$
$\displaystyle=\frac{1}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\pi_{a}^{\ell}$
$\displaystyle=\left(\frac{\pi_{a}+1}{|\pi|+1}\right)^{k},$

as desired. ∎

We can now compute sufficiently strong bounds on the eigenvalues in general.
We decompose the eigenvalues as follows. We have

$\operatorname{eig}(T)=F_{0}(T)+F_{+}(T),$ (6)

where

$\displaystyle F_{0}(T)$
$\displaystyle:=\frac{1}{n}\sum_{i=0}^{n-1}\nu(\lambda^{(i)},a^{(i)},0)=\frac{1}{n}\sum_{\text{boxes
}(i,j)\in T}\frac{j^{k}}{T(i,j)^{k}},$ (7) $\displaystyle F_{+}(T)$
$\displaystyle:=\frac{1}{n}\sum_{u=1}^{k}\sum_{i=0}^{n-1}\nu(\lambda^{(i)},a^{(i)},u).$

Recall that $T(i,j)$ denotes the value in box $(i,j)$ of $T.$ We used
Proposition 13 to give the simplified expression for $F_{0}(T)$ in (7). The
next two results give effective upper and lower bounds on $F_{0}(T)$ and
$F_{+}(T).$ Notably, both depend on $T(2,1).$ This will guide our later
calculations. It will turn out that $F_{0}(T)$ gives the main term of
$\operatorname{eig}(T).$

######  Proposition 14.

For $T\in\operatorname{SYT}(\lambda)$ where $\lambda\vdash n$ and
$\lambda_{1}=n-m,$ we have

$0<F_{0}(T)<1-\frac{m}{n}-\frac{n-m-T(2,1)+1}{n}\cdot\frac{k}{2n}+2^{1-k}.$

###### Proof.

Clearly $F_{0}(T)>0,$ so we focus on the upper bound. Using Proposition 13 and
splitting the summation into contributions by row one and other contributions,

$\displaystyle F_{0}(T)$ $\displaystyle=\frac{1}{n}\sum_{\text{boxes }(1,j)\in
T}\frac{j^{k}}{T(1,j)^{k}}+\frac{1}{n}\sum_{\begin{subarray}{c}\text{boxes
}(i,j)\in T\\\ i\geq 2\end{subarray}}\frac{j^{k}}{T(i,j)^{k}}.$

For $i\geq 2,$ we have $j\leq\frac{T(i,j)}{2}$ (since $\lambda$ is a
partition), so the second summation is at most $n2^{1-k}.$ For the first
summation, we notice that $T(1,j)=j\mbox{ if }j<T(2,1)$ and $T(1,j)\leq
j+1\mbox{ if }j\geq T(2,1)$. Therefore,

$\displaystyle\sum_{\text{boxes }(1,j)\in T}\frac{j^{k}}{T(1,j)^{k}}$
$\displaystyle\leq T(2,1)-1+(n-m-T(2,1)+1)\cdot\left(\frac{n-1}{n}\right)^{k}$
$\displaystyle=n-m-(n-m-T(2,1)+1)\cdot\frac{n^{k}-(n-1)^{k}}{n^{k}}.$

Finally, we have

$\displaystyle\frac{n^{k}-(n-1)^{k}}{n^{k}}$
$\displaystyle\geq\frac{k}{n}\cdot\frac{(n-1)^{k-1}}{n^{k-1}}=\frac{k}{n}\left(1-\frac{1}{n}\right)^{k-1}\geq\frac{k}{2n},$

from which the result follows. ∎

The next proposition says that $F_{+}(T)$ essentially gives an error term of
$\operatorname{eig}(T),$ though some level of precision is required.

######  Proposition 15.

For $T\in\operatorname{SYT}(\lambda)$ where $\lambda\vdash n,$ we have

$-\frac{2\log n}{n}<F_{+}(T)<\frac{1}{n}.$ (8)

Furthermore, for any constant $c>1,$ when $T(2,1)>\frac{n}{c},$

$F_{+}(T)<O\left(\frac{1}{n^{2}}\right).$ (9)

###### Proof.

We prove the lower bound first.

$\displaystyle F_{+}(T)$
$\displaystyle=\frac{1}{n}\sum_{u=1}^{k}\sum_{i=0}^{n-1}\nu(\lambda^{(i)},a^{(i)},u)\geq-\frac{1}{n}\sum_{u=1}^{k}\sum_{i=0}^{n-1}\left|\nu(\lambda^{(i)},a^{(i)},u)\right|=-\frac{1}{n}\left(\nu(\lambda^{(1)},a^{(1)},1)+\sum_{u=1}^{k}\sum_{i=2}^{n-1}\left|\nu(\lambda^{(i)},a^{(i)},u)\right|\right),$

where in the last equation we used that $\nu(\lambda^{(0)},a^{(0)},u)=0$ for
all $u\geq 1$ and $\nu(\lambda^{(1)},a^{(1)},u)=0$ for all $u\geq 2$
(Proposition 11). Applying Proposition 12, while noting that
$|\lambda^{(i)}|=i$, we have that

$\displaystyle
F_{+}(T)\geq-\frac{1}{n}\left(1+\sum_{u=1}^{k}\sum_{i=2}^{n-1}i^{-u}\right)$
$\displaystyle\geq-\frac{1}{n}\left(1+\sum_{i=2}^{n-1}\frac{1}{i-1}\right)>-\frac{2\log
n}{n},$

showing the lower bound in (8). To show the upper bound in (8), we similarly
compute

$\displaystyle
F_{+}(T)=\frac{1}{n}\sum_{u=1}^{k}\sum_{i=0}^{n-1}\nu(\lambda^{(i)},a^{(i)},u)\leq\frac{1}{n}\sum_{u=2}^{k}\sum_{i=2}^{n-1}\left|\nu(\lambda^{(i)},a^{(i)},u)\right|,$

where we used that $\nu(\lambda^{(i)},a^{(i)},1)\leq 0$ (Proposition 12), and
that $\nu(\lambda^{(i)},a^{(i)},u)=0$ for $i=0,1$ and $u\geq 1$ (Proposition
11). Applying Proposition 12 again, we get

$\displaystyle
F_{+}(T)\leq\frac{1}{n}\sum_{u=2}^{k}\sum_{i=2}^{n-1}i^{-u}\leq\frac{1}{n}\sum_{i=2}^{n-1}\frac{1}{i(i-1)}<\frac{1}{n}.$

Finally, to show (9), assume additionally that $T(2,1)>\frac{n}{c}$ for a
constant $c>1.$ Thus,

$\displaystyle
F_{+}(T)=\frac{1}{n}\sum_{u=1}^{k}\sum_{i=0}^{n-1}\nu(\lambda^{(i)},a^{(i)},u)\leq\frac{1}{n}\sum_{u=2}^{k}\sum_{i=\frac{n}{c}}^{n-1}\left|\nu(\lambda^{(i)},a^{(i)},u)\right|,$

where we’ve used the same observations as above, in addition to that for
$i\leq\frac{n}{c}$ and $u\geq 1,$ we have $u\geq a^{(i)}=1$ which implies
$\nu(\lambda^{(i)},a^{(i)},u)=0$ (Proposition 11). Proposition 12 gives that

$\displaystyle
F_{+}(T)\leq\frac{1}{n}\sum_{u=2}^{k}\sum_{i=\frac{n}{c}}^{n-1}i^{-u}\leq\frac{1}{n}\sum_{i=\frac{n}{c}}^{n-1}\frac{1}{i(i-1)}=\frac{1}{n}\left(\frac{1}{\frac{n}{c}-1}-\frac{1}{n-1}\right)=O\left(\frac{1}{n^{2}}\right).$

∎

##  4 Upper bound in the general case

In this section, we show Theorem 2(i), which states that $P_{n,k}$ mixes in at
most $n\log n+cn$ time for all $k\geq 1.$ This makes sense intuitively, as the
case $k=1$ was shown in [12], and we would expect more transpositions at each
step to only speed up the shuffle. The result follows from the following
lemma, which provides general bounds on the eigenvalues of $P_{n,k}.$

######  Lemma 16.

Assume $k\geq 1.$ Then for $T\in\operatorname{SYT}(\lambda)$ where
$\lambda\vdash n$ with $\lambda_{1}=n-m,$

$\left|\operatorname{eig}(T)\right|\leq\begin{cases}\frac{n-m}{n}+\frac{1}{n}\sum_{j=1}^{m}\frac{j-1}{n-m+j}+O(\frac{1}{n^{2}}),&\textup{if
}m\leq\frac{n}{2}\\\
\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j-1}{n-m+j}+\frac{n-2(n-m)}{3n},&\textup{otherwise.}\end{cases}$

To show Theorem 2 from the bounds in Lemma 16, we refer the reader to the
analysis given in Section 2.2 of [12], where these bounds are used in
combination with (1) to provide the desired result. The only way the analysis
differs in our case is that we have an additional $O(\frac{1}{n^{2}})$ term
when $m\leq\frac{n}{2}$. Unsurprisingly, the small difference is
inconsequential, only resulting in a change in the universal constant $A$.
Thus, we devote the remainder of this section to proving Lemma 16.

The following type of standard Young tableaux will be useful to define.

######  Definition 17.

For $\lambda\vdash n$ with $\lambda_{1}=n-m$ and $2\leq s\leq n-m+1,$ define
$T^{\rightarrow}_{\lambda,s}$ to be the SYT constructed by inserting the
numbers $1,\cdots,n$ from left to right with the exception that $T(2,1)=s.$

For example, if $\lambda=(6,4,2)$ and $s=4,$ we have

$T^{\rightarrow}_{\lambda,s}=\ytableaushort{123567,489{10},{11}{12}}.$

We are especially interested in the case
$\lambda=(n-m,*):=(n-m,n-m,\cdots,n-m,p),$ the partition with the maximum
possible number of rows of size $n-m$ followed by one row with the remainder.
In particular, $(n-m,*)=(n-m,m)$ when $m\leq\frac{n}{2}.$

######  Lemma 18.

For all $T\in\operatorname{SYT}(\lambda)$ with $\lambda_{1}=n-m$ and
$T(2,1)=s,$ we have $F_{0}(T)\leq F_{0}(T_{(n-m,*),s}^{\rightarrow}).$

The proof presented below follows the outline of those of Lemma 9 and Lemma 12
in [12].

###### Proof.

It suffices to show that $F_{0}(T)\leq F_{0}(T_{\lambda,s}^{\rightarrow})$ and
$F_{0}(T_{\lambda,s}^{\rightarrow})\leq F_{0}(T_{(n-m,*),s}^{\rightarrow}).$
To show the first inequality, we describe a process that transforms $T$ to
$T_{\lambda,s}^{\rightarrow}$ such that $F_{0}$ is monotonically increasing.
Starting from the first row and moving from left to right, let $(i,j)$ be the
first box where $T(i,j)\neq T_{\lambda,s}^{\rightarrow}(i,j).$ Then let
$T^{\prime}$ be the standard Young tableau obtained by swapping the entries
$T(i,j)$ and $T(i^{\prime},j^{\prime})$ in $T$ where
$T(i^{\prime},j^{\prime})=T(i,j)-1$. Observe that $j>j^{\prime}.$ Using the
definition of $F_{0}(T)$, we get

$\displaystyle F_{0}(T^{\prime})-F_{0}(T)$
$\displaystyle=\frac{1}{n}\left[\left(\frac{j^{\prime}}{T(i,j)}\right)^{k}+\left(\frac{j}{T(i^{\prime},j^{\prime})}\right)^{k}-\left(\frac{j}{T(i,j)}\right)^{k}-\left(\frac{j^{\prime}}{T(i^{\prime},j^{\prime})}\right)^{k}\right]$
$\displaystyle=\frac{1}{n}(j^{k}-j^{\prime
k})\left(\frac{1}{T(i^{\prime},j^{\prime})^{k}}-\frac{1}{T(i,j)^{k}}\right)\geq
0.$

Continuing this process, we eventually obtain $T_{\lambda,s}^{\rightarrow}$,
which shows that $F_{0}(T)\leq F_{0}(T_{\lambda,s}^{\rightarrow})$.

To show that $F_{0}(T_{\lambda,s}^{\rightarrow})\leq
F_{0}(T_{(n-m,*),s}^{\rightarrow}),$ it suffices to show that
$F_{0}(T_{\lambda,s}^{\rightarrow})\geq F_{0}(T_{\mu,s}^{\rightarrow})$ when
$\mu$ is a partition obtained from $\lambda$ by moving one box down one row.
Suppose that we move the box in position to $(a,\lambda_{a})$ to
$(a+1,\lambda_{a+1}+1),$ which means that $\lambda_{a}\geq\lambda_{a+1}+2.$ If
we set $b=2$ if $a=1$, and $b=1$ otherwise (this accounts for $T(2,1)$
remaining fixed when a box is moved from row one to row two), then

$\displaystyle
F_{0}(T_{\lambda,s}^{\rightarrow})-F_{0}(T_{\mu,s}^{\rightarrow})$
$\displaystyle=\frac{\lambda_{a}^{k}}{T_{\lambda,s}(a,\lambda_{a})^{k}}-\frac{(\lambda_{a+1}+1)^{k}}{T_{\mu,s}(a+1,\lambda_{a+1}+1)^{k}}+\sum_{j=b}^{\lambda_{a+1}}\left(\frac{j^{k}}{T_{\lambda,s}(a+1,j)^{k}}-\frac{j^{k}}{T_{\mu,s}(a+1,j)^{k}}\right)$
$\displaystyle\geq\frac{\lambda_{a}^{k}}{T_{\lambda,s}(a,\lambda_{a})^{k}}-\frac{(\lambda_{a+1}+1)^{k}}{T_{\mu,s}(a+1,\lambda_{a+1}+1)^{k}}+\lambda_{a}^{k}\sum_{j=b}^{\lambda_{a+1}}\left(\frac{1}{T_{\lambda,s}(a+1,j)^{k}}-\frac{1}{T_{\mu,s}(a+1,j)^{k}}\right)$
(10)
$\displaystyle=\frac{\lambda_{a}^{k}}{T_{\lambda,s}(a,\lambda_{a})^{k}}-\frac{(\lambda_{a+1}+1)^{k}}{T_{\mu,s}(a+1,\lambda_{a+1}+1)^{k}}+\lambda_{a}^{k}\left(\frac{1}{T_{\mu,s}(a+1,\lambda_{a+1}+1)^{k}}-\frac{1}{T_{\lambda,s}(a,\lambda_{a})^{k}}\right)$
(11)
$\displaystyle=\frac{\lambda_{a}^{k}-(\lambda_{a+1}+1)^{k}}{T_{\mu,s}(a+1,\lambda_{a+1}+1)^{k}}\geq
0.$

Here, (10) follows by bounding $j^{k}$ from above by $\lambda_{a}^{k}$ (note
that the summand is always negative) and (11) follows by telescoping the
resulting sum. ∎

The following result follows almost immediately.

######  Proposition 19.

For all $T\in\operatorname{SYT}(\lambda)$ where $\lambda_{1}=n-m$ and
$T(2,1)=s,$

$\operatorname{eig}(T)\leq F_{0}(T_{(n-m,*),s}^{\rightarrow})+\frac{1}{n}.$
(12)

Moreover, when $T(2,1)>\frac{n}{c}$ for a constant $c>1,$

$\operatorname{eig}(T)\leq
F_{0}(T_{(n-m,*),s}^{\rightarrow})+O\left(\frac{1}{n^{2}}\right).$ (13)

###### Proof.

After recalling from (6) that $\operatorname{eig}(T)=F_{0}(T)+F_{+}(T)$, the
result follows directly from Lemma 18 and Proposition 15. ∎

Thus, we turn our attention towards $F_{0}(T_{(n-m,*),s}^{\rightarrow})$.
Below, we will often abbreviate $T_{(n-m,*),s}^{\rightarrow}$ to
$T_{s}^{\rightarrow}$.

######  Proposition 20.

Let $s\geq 2$ and $T\in\operatorname{SYT}(\lambda)$ with $\lambda_{1}=n-m$ and
$T(2,1)=s.$ Whenever $m\leq\frac{n}{2},$

$\displaystyle F_{0}(T_{s}^{\rightarrow})$
$\displaystyle\leq\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{m}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}+\frac{1}{ns^{2}},$
(14)

and when $m>\frac{n}{2},$

$\displaystyle F_{0}(T_{s}^{\rightarrow})$
$\displaystyle\leq\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}+\frac{1}{ns^{2}}+\frac{n-2(n-m)}{9n}.$
(15)

###### Proof.

Equation (14) follows by noting that

$F_{0}(T_{s}^{\rightarrow})=\frac{1}{n}\sum_{\text{boxes
}(i,j)}\frac{j^{k}}{T_{s}^{\rightarrow}(i,j)^{k}}\leq\frac{1}{n}\sum_{\text{boxes
}(i,j)}\frac{j^{2}}{T_{s}^{\rightarrow}(i,j)^{2}}$

and breaking the sum up by $i$, and noting that $T(2,1)=s$, and that in this
case $T_{s}^{\rightarrow}$ has two rows. To show (15), we additionally note
that $\frac{j^{2}}{T_{s}^{\rightarrow}(i,j)^{2}}\leq\frac{1}{9}$ when $i\geq
3.$ ∎

We now prove the following technical lemma which will be useful in the proof
of Lemma 16.

######  Proposition 21.

For all $m\in[n-1]$ and $p,s\geq 2,$

$\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{p}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{p}\frac{j-1}{n-m+j}-\frac{0.9}{n}\log\frac{n-m}{s}.$

###### Proof of Proposition 21..

For $j\geq 2,$
$\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}\leq\frac{j-1}{T_{s}^{\rightarrow}(2,j)}$
since $T_{s}(2,j)\geq 2j.$ Therefore,

$\sum_{j=2}^{p}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}-\sum_{j=2}^{p}\frac{j-1}{T_{s}^{\rightarrow}(2,j)}\leq
0.$

Also,

$\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}-\frac{1}{n}\sum_{j=1}^{n-m}\frac{j}{T_{s}^{\rightarrow}(1,j)}<\frac{1}{n}\int_{s+1}^{n-m+1}\frac{x^{2}}{(x+1)^{2}}-\frac{x}{x+1}\,dx<-\frac{0.9}{n}\log\frac{n-m}{s}.$

Thus,

$\displaystyle\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{p}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}$
$\displaystyle<\frac{1}{n}\sum_{j=1}^{n-m}\frac{j}{T_{s}^{\rightarrow}(1,j)}+\frac{1}{n}\sum_{j=2}^{p}\frac{j-1}{T_{s}^{\rightarrow}(2,j)}-\frac{0.9}{n}\log\frac{n-m}{s}.$

The result follows after noticing that

$\frac{1}{n}\sum_{j=1}^{n-m}\frac{j}{T_{s}^{\rightarrow}(1,j)}\leq\frac{n-m}{n},$

as $\frac{j}{T_{s}^{\rightarrow}(1,j)}\leq 1,$ and

$\frac{1}{n}\sum_{j=2}^{p}\frac{j-1}{T_{s}^{\rightarrow}(2,j)}\leq\frac{1}{n}\sum_{j=2}^{p}\frac{j-1}{n-m+j},$

as $T_{s}^{\rightarrow}(2,j)\geq n-m+j.$ ∎

We now prove Lemma 16 using Proposition 19, Proposition 20, and Proposition
21.

###### Proof of Lemma 16.

We will consider five “zones” of standard Young tableau depending on the size
of the first row and on the value of $T(2,1).$ In each case, the result will
follow quickly from the results established above.

#### 1\. Large first part, small $T(2,1)$.

When $m\leq\frac{n}{2}$ and $2\leq s\leq\frac{n}{100},$

$\displaystyle\operatorname{eig}(T)$ $\displaystyle\leq
F_{0}(T_{s}^{\rightarrow})+\frac{1}{n}$ from (12)
$\displaystyle<\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{m}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}+\frac{1}{4n}+\frac{1}{n}$
from (14)
$\displaystyle<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{m}\frac{j-1}{n-m+j}-\frac{0.9\log
50}{n}+\frac{5}{4n}$ from Proposition 21
$\displaystyle<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{m}\frac{j-1}{n-m+j}.$

#### 2\. Large first part, large $T(2,1)$.

When $m\leq\frac{n}{2}$ and $s>\frac{n}{100},$

$\displaystyle\operatorname{eig}(T)$ $\displaystyle\leq
F_{0}(T_{s}^{\rightarrow})+O\left(\frac{1}{n^{2}}\right)$ from (13)
$\displaystyle<\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{m}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}+O\left(\frac{1}{n^{2}}\right)$
from (14)
$\displaystyle<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{m}\frac{j-1}{n-m+j}+O\left(\frac{1}{n^{2}}\right)$
$\displaystyle\qquad\text{from \lx@cref{creftypecap~refnum}{eq:general-final-
bound}}.$

#### 3\. Small first part, small $T(2,1)$.

When $\frac{n}{2}<m<\frac{9n}{10}$ and $2\leq s\leq\frac{n}{100},$

$\displaystyle\operatorname{eig}(T)$ $\displaystyle\leq
F_{0}(T_{s}^{\rightarrow})+\frac{1}{n}$ from (12)
$\displaystyle<\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}+\frac{1}{4n}+\frac{n-2(n-m)}{9n}+\frac{1}{n}$
from (15)
$\displaystyle<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j-1}{n-m+j}-\frac{0.9\log
10}{n}+\frac{5n}{4}+\frac{n-2(n-m)}{9n}$ from Proposition 21
$\displaystyle<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j-1}{n-m+j}+\frac{n-2(n-m)}{3n}.$

#### 4\. Small first part, large $T(2,1)$.

When $\frac{n}{2}<m<\frac{9n}{10}$ and $s>\frac{n}{100},$

$\displaystyle\operatorname{eig}(T)$ $\displaystyle\leq
F_{0}(T_{s}^{\rightarrow})+O\left(\frac{1}{n^{2}}\right)$ from (13)
$\displaystyle<\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}+\frac{n-2(n-m)}{9n}+O\left(\frac{1}{n^{2}}\right)$
from (15)
$\displaystyle<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j-1}{n-m+j}+\frac{n-2(n-m)}{9n}+O\left(\frac{1}{n^{2}}\right)$
from Proposition 21
$\displaystyle<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j-1}{n-m+j}+\frac{n-2(n-m)}{3n}.$

#### 5\. Very small first part.

When $m\geq\frac{9n}{10}$ and $s\geq 2,$

$\displaystyle\operatorname{eig}(T)$ $\displaystyle\leq
F_{0}(T_{s}^{\rightarrow})+\frac{1}{n}$ from (12)
$\displaystyle<\frac{1}{n}\sum_{j=1}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(1,j)^{2}}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j^{2}}{T_{s}^{\rightarrow}(2,j)^{2}}+\frac{1}{4n}+\frac{n-2(n-m)}{9n}+\frac{1}{n}$
from (15)
$\displaystyle\leq\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j-1}{n-m+j}+\frac{5n}{4}-\frac{8}{45}+\frac{n-2(n-m)}{3n}$
$\displaystyle<\frac{n-m}{n}+\frac{1}{n}\sum_{j=2}^{n-m}\frac{j-1}{n-m+j}+\frac{n-2(n-m)}{3n},$

where we used that $\frac{n-2(n-m)}{3n}-\frac{n-2(n-m)}{9n}\geq\frac{8}{45}.$
∎

##  5 Upper bound when $k=n^{\gamma}$ with $\gamma\in(0,1]$

In this section, we prove Theorem 2(ii). Throughout, we will assume that
$k=n^{\gamma}$ with $\gamma\in(0,1]$. It suffices to bound

$\sum_{\begin{subarray}{c}\lambda\vdash n\\\
\lambda\neq(n)\end{subarray}}d_{\lambda}\sum_{T\in\operatorname{SYT}(\lambda)}\operatorname{eig}(T)^{2t}.$
(16)

We split this summation into three parts based on the size of the first part
of $\lambda.$ In the sections below, we show that when
$t=(1-\frac{\gamma}{2})n\log n+cn,$ the following bounds hold for $c>3$ and
$n$ sufficiently large:

$\displaystyle\sum_{m=1}^{\frac{n^{\gamma}}{13}}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\
\lambda_{1}=n-m\end{subarray}}d_{\lambda}\sum_{T\in\operatorname{SYT}(\lambda)}\operatorname{eig}(T)^{2t}\right)$
$\displaystyle<(e+2)e^{-c}\quad\qquad$ Large first part — §5.1 (17)
$\displaystyle\sum_{m=\frac{n^{\gamma}}{13}}^{(1-\frac{1}{e})n}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\
\lambda_{1}=n-m\end{subarray}}d_{\lambda}\sum_{T\in\operatorname{SYT}(\lambda)}\operatorname{eig}(T)^{2t}\right)$
$\displaystyle<4e^{-c}\quad\qquad$ Small first part — §5.2 (18)
$\displaystyle\sum_{m=(1-\frac{1}{e})n}^{n-1}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\
\lambda_{1}=n-m\end{subarray}}d_{\lambda}\sum_{T\in\operatorname{SYT}(\lambda)}\operatorname{eig}(T)^{2t}\right)$
$\displaystyle<e^{-c}\quad\qquad$ Very small first part — §5.3 (19)

Together, these prove Theorem 2(ii).

###  5.1 Large first part: $1\leq m\leq\frac{n^{\gamma}}{13}$

Throughout this section, we consider $\lambda$ such that $\lambda_{1}=n-m$
where $1\leq m\leq\frac{n^{\gamma}}{13}$. It will be useful to split up the
tableau in $\operatorname{SYT}(\lambda)$ into two types:

$\displaystyle\operatorname{SYT}_{1}(\lambda)$ $\displaystyle:=\\{T:T(2,1)\leq
n-m-6mn^{1-\gamma}\\}$ $\displaystyle\operatorname{SYT}_{2}(\lambda)$
$\displaystyle:=\\{T:T(2,1)>n-m-6mn^{1-\gamma}\\}$

The next lemma shows most $T\in\operatorname{SYT}(\lambda)$ are in
$\operatorname{SYT}(T_{1}).$

######  Lemma 22 (Most tableaux are in $\operatorname{SYT}_{1}$).

For $\lambda\vdash n$ such that $\lambda_{1}=n-m$ where $1\leq
m\leq\frac{n^{\gamma}}{13}$,

$\frac{|\operatorname{SYT}_{2}(\lambda)|}{d_{\lambda}}\leq(12mn^{-\gamma})^{m},$

where we recall that $d_{\lambda}:=\operatorname{SYT}(\lambda).$

###### Proof.

Let $\mathcal{S}\subset\operatorname{SYT}(\lambda)$ be a set of all tableaux
in $\operatorname{SYT}(T)$ where the elements in row two and below have some
fixed ordering. We show that a randomly chosen tableau in $\mathcal{S}$ is in
$\operatorname{SYT}_{2}(\lambda)$ with probability at most
$(12mn^{-\gamma})^{m}$. Since $\operatorname{SYT}(\lambda)$ can be partitioned
into such sets $\mathcal{S}$, this proves the result.

Note that $|\mathcal{S}|\geq\binom{n-m}{m}$ since every choice of $m$ distinct
elements in $\\{m+1,m+2,\cdots,n\\}$ corresponds to a unique SYT in
$\mathcal{S}$ with these elements below row one. By similar logic, the number
of SYT in $\mathcal{S}$ with $T(2,1)>n-m-6mn^{1-\gamma}$ is exactly
$\binom{6mn^{1-\gamma}}{m}.$ The result follows, since

$\frac{\binom{6mn^{1-\gamma}}{m}}{\binom{n-m}{m}}\leq\frac{\binom{6mn^{1-\gamma}}{m}}{\binom{n/2}{m}}\leq(12mn^{-\gamma})^{m}.$

∎

The next lemma bounds $\operatorname{eig}(T)$ depending on if $T$ is in
$\operatorname{SYT}_{1}(\lambda)$ or $\operatorname{SYT}_{2}(\lambda).$

######  Lemma 23 (Eigenvalue bounds for $\operatorname{SYT}_{1}$ and
$\operatorname{SYT}_{2}$).

Consider $\lambda\vdash n$ such that $\lambda_{1}=n-m$ where $1\leq
m\leq\frac{n^{\gamma}}{13}$. Then

$\left|\operatorname{eig}(T)\right|\leq\begin{cases}1-\frac{2m}{n}+O\left(\frac{1}{n^{2}}\right)&\text{for
}T\in\operatorname{SYT}_{1}(\lambda)\\\
1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)&\text{for
}T\in\operatorname{SYT}_{2}(\lambda)\end{cases}.$

###### Proof.

In both cases, we simply write $\operatorname{eig}(T)=F_{0}(T)+F_{+}(T)$ and
apply Proposition 14 and Proposition 15. These propositions immediately give
$\operatorname{eig}(T)>-\frac{2\log n}{n}$, which is much less in absolute
value than both $1-\frac{2m}{n}+O\left(\frac{1}{n^{2}}\right)$ and
$1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)$, so it suffices to upper bound
$\operatorname{eig}(T)$ in each case.

For $T\in\operatorname{SYT}_{1}(\lambda),$ $n-m-T(2,1)+1\geq 6mn^{1-\gamma}$.
Applying Proposition 14,

$\displaystyle F_{0}(T)$ $\displaystyle\leq
1-\frac{m}{n}-\frac{6mn^{1-\gamma}n^{\gamma-1}}{2n}+2^{1-k}$
$\displaystyle\leq 1-\frac{4m}{n}+2^{1-k}$

Furthermore, $F_{+}(T)\leq\frac{2}{n}$ by Proposition 15. Thus,

$\displaystyle\operatorname{eig}(T)=F_{0}(T)+F_{+}(T)$ $\displaystyle\leq
1-\frac{4m}{n}+2^{1-k}+\frac{2}{n}$ $\displaystyle\leq
1-\frac{2m}{n}+O\left(\frac{1}{n^{2}}\right),$

where in the last line we used that $2^{1-k}=O\left(\frac{1}{n^{2}}\right)$.

For $T\in\operatorname{SYT}_{2}(\lambda),$

$T(2,1)\geq n-m-6mn^{1-\gamma}\geq n-m-\frac{6n}{13}>\frac{n}{2}.$

Applying Proposition 15, $F_{+}(T)\leq O\left(\frac{1}{n^{2}}\right).$
Applying Proposition 14, $F_{0}(T)\leq 1-\frac{m}{n}+2^{1-k}.$ Thus,

$\displaystyle\operatorname{eig}(T)=F_{0}(T)+F_{+}(T)$ $\displaystyle\leq
1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right),$

again observing that $2^{1-k}=O\left(\frac{1}{n^{2}}\right)$. ∎

Together, the above two lemmas show that—in essence—almost all eigenvalues are
from $\operatorname{SYT}_{1}(\lambda)$ and are very small, while a small
number of eigenvalues are from $\operatorname{SYT}_{2}(\lambda)$ and are
somewhat larger.

###### Proof of (17)..

We will split the summation in (17) depending on if $T$ is in
$\operatorname{SYT}_{1}(\lambda)$ or $\operatorname{SYT}_{2}(\lambda)$.
Beginning with the first case,

$\displaystyle\sum_{m=1}^{\frac{n^{\gamma}}{13}}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\
\lambda_{1}=n-m\end{subarray}}d_{\lambda}\sum_{T\in\operatorname{SYT}_{1}(\lambda)}\operatorname{eig}(T)^{2t}\right)$
$\displaystyle\leq\sum_{m=1}^{\frac{n^{\gamma}}{13}}\left(1-\frac{2m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t}\sum_{\begin{subarray}{c}\lambda\vdash
n\\\
\lambda_{1}=n-m\end{subarray}}|\operatorname{SYT}_{1}(\lambda)|d_{\lambda}$
(20)
$\displaystyle\leq\sum_{m=1}^{\frac{n^{\gamma}}{13}}\left(1-\frac{2m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\ \lambda_{1}=n-m\end{subarray}}d_{\lambda}^{2}\right)$ (21)
$\displaystyle\leq\sum_{m=1}^{\frac{n^{\gamma}}{13}}\frac{n^{2m}}{m!}\left(1-\frac{2m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t},$
(22)

where (20) follows from Lemma 23, (21) follows from the bound
$|\operatorname{SYT}_{1}(\lambda)|\leq|\operatorname{SYT}(\lambda)|=d_{\lambda}$,
and (22) follows from Proposition 6. Taking $t=\frac{1}{2}n\log n+cn,$ this is
at most

$\displaystyle\sum_{m=1}^{\frac{n^{\gamma}}{13}}\frac{n^{2m}}{m!}e^{-(n\log
n+2cn)\left(\frac{2m}{n}-O\left(\frac{1}{n^{2}}\right)\right)}$
$\displaystyle=\sum_{m=1}^{\frac{n^{\gamma}}{13}}\frac{n^{2m}}{m!}n^{-2m+O\left(\frac{1}{n}\right)}e^{-2mc+cO\left(\frac{1}{n}\right)}$
$\displaystyle=\sum_{m=1}^{\frac{n^{\gamma}}{13}}e^{-2mc+cO\left(\frac{1}{n}\right)}\frac{n^{O\left(\frac{1}{n}\right)}}{m!}$
$\displaystyle<\sum_{m=1}^{\frac{n^{\gamma}}{13}}\frac{2e^{-c}}{m!}$ (23)
$\displaystyle<2(e-1)e^{-c},$ (24)

where (23) follows from the crude observations that for $n$ sufficiently
large, $n^{O\left(\frac{1}{n}\right)}<2$ and
$e^{-2mc+cO\left(\frac{1}{n}\right)}<e^{-c}$. Equation (24) follows from the
Taylor expansion of $e^{x}.$

In the second case, where $T\in\operatorname{SYT}_{2}(\lambda)$, we have

$\displaystyle\sum_{m=1}^{\frac{n^{\gamma}}{13}}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\
\lambda_{1}=n-m\end{subarray}}d_{\lambda}\sum_{T\in\operatorname{SYT}_{2}(\lambda)}\operatorname{eig}(T)^{2t}\right)$
$\displaystyle\leq\sum_{m=1}^{\frac{n^{\gamma}}{13}}\left(1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t}\sum_{\begin{subarray}{c}\lambda\vdash
n\\\ \lambda_{1}=n-m\end{subarray}}|\operatorname{SYT}_{2}|d_{\lambda}$ (25)
$\displaystyle\leq\sum_{m=1}^{\frac{n^{\gamma}}{13}}\left(1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\ \lambda_{1}=n-m\end{subarray}}(12mn^{-\gamma})^{m}d_{\lambda}^{2}\right)$
(26)
$\displaystyle\leq\sum_{m=1}^{\frac{n^{\gamma}}{13}}\frac{n^{2m}}{m!}\cdot(12mn^{-\gamma})^{m}\cdot\left(1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t},$
(27)

where (25) follows from Lemma 23, (26) follows from Lemma 22, and (27) follows
from Proposition 6. Using the bound $m!\geq m^{m}e^{1-m}$, this is at most

$\displaystyle\sum_{m=1}^{\frac{n^{\gamma}}{13}}(12mn^{-\gamma})^{m}n^{2m}m^{-m}e^{m-1}\left(1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t}.$

Taking $t=(1-\frac{\gamma}{2})n\log n+cn$, this is at most

$\displaystyle\sum_{m=1}^{\frac{n^{\gamma}}{13}}(12mn^{-\gamma})^{m}n^{2m}m^{-m}e^{m-1}e^{-((2-\gamma)n\log
n+2cn)\left(\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)\right)}$
$\displaystyle=\sum_{m=1}^{\frac{n^{\gamma}}{13}}12^{m}e^{-2mc+m-1+cO\left(\frac{1}{n}\right)}n^{O\left(\frac{1}{n}\right)}$
$\displaystyle<\,2\sum_{m=1}^{\frac{n^{\gamma}}{13}}e^{-2mc+(1+\log
12)m-1+cO\left(\frac{1}{n}\right)},$

where in the last line we used that $n^{O\left(\frac{1}{n}\right)}<2$ for $n$
sufficiently large. Now, whenever $c>3$ and $n$ is sufficiently large, the
remaining expression is less than

$\displaystyle
2\sum_{m=1}^{\frac{n^{\gamma}}{13}}e^{-mc}<2\sum_{m=1}^{\infty}e^{-mc}<4e^{-c}.$

Combining the two cases completes our calculation. ∎

###  5.2 Small first part ($\frac{n^{\gamma}}{13}\leq
m\leq\lceil(1-\frac{1}{e})n\rceil+2$)

We begin by bounding the eigenvalues in this case.

######  Lemma 24.

Consider $\lambda\vdash n$ such that $\lambda_{1}=n-m$ where
$\frac{n^{\gamma}}{13}\leq m\leq\lceil(1-\frac{1}{e})n\rceil+2.$ Then for
$T\in\operatorname{SYT}(\lambda),$ we have

$\left|\operatorname{eig}(T)\right|<1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right),$

when $n$ is sufficiently large.

###### Proof.

As in the proof of Lemma 23, it suffices to show an upper bound. Consider two
cases: $T(2,1)\geq\frac{n}{3}$ and $T(2,1)<\frac{n}{3}.$ After writing
$\operatorname{eig}(T)=F_{0}(T)+F_{+}(T),$ the first case is an immediate
result of Proposition 14 and Proposition 15 (with $c=3$).

For the second case, we also apply Proposition 14 and Proposition 15 to get

$\displaystyle\operatorname{eig}(T)=F_{0}(T)+F_{+}(T)$
$\displaystyle<1-\frac{m}{n}-\frac{n-m-T(2,1)}{n}\cdot
n^{\gamma-1}+2^{1-k}+\frac{1}{n}.$

Because $T(2,1)<\frac{n}{3}$, this is less than

$\displaystyle 1-\frac{m}{n}-\frac{2n/3-m}{n}\cdot
n^{\gamma-1}+2^{1-k}+\frac{1}{n}$
$\displaystyle<1-\frac{m}{n}-0.034n^{\gamma-1}+2^{1-k}+\frac{1}{n}$ (28)
$\displaystyle<1-\frac{m}{n}+2^{1-k},$ (29)

where (28) follows because $m<(1-\frac{1}{e})n+3$ (from our assumptions on
$\lambda$), and (29) follows because $0.034n^{\gamma-1}>\frac{1}{n}$ for $n$
sufficiently large and $2^{1-k}=O\left(\frac{1}{n^{2}}\right)$. ∎

We proceed to the main calculation.

###### Proof of (18).

Applying Lemma 24, we find

$\displaystyle\sum_{m=\frac{n^{\gamma}}{13}}^{\lceil(1-\frac{1}{e})n\rceil+2}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\
\lambda_{1}=n-m\end{subarray}}d_{\lambda}\sum_{T\in\operatorname{SYT}(\lambda)}\operatorname{eig}(T)^{2t}\right)$
$\displaystyle\leq\sum_{m=\frac{n^{\gamma}}{13}}^{\lceil(1-\frac{1}{e})n\rceil+2}\frac{n^{2m}}{m!}\left(1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t}$
(30)
$\displaystyle\leq\sum_{m=\frac{n^{\gamma}}{13}}^{\lceil(1-\frac{1}{e})n\rceil+2}n^{2m}m^{-m}e^{m-1}\left(1-\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)\right)^{2t},$
(31)

where (30) follows from Proposition 6 and (31) follows from the bound $m!\geq
m^{m}e^{1-m}$. Continuing, and taking $t=(1-\frac{\gamma}{2})n\log n+cn,$ this
is less than

$\displaystyle\sum_{m=\frac{n^{\gamma}}{13}}^{\lceil(1-\frac{1}{e})n\rceil+2}n^{2m}m^{-m}e^{m-1}e^{-((2-\gamma)n\log
n+2cn)\left(\frac{m}{n}+O\left(\frac{1}{n^{2}}\right)\right)}$
$\displaystyle=\sum_{m=\frac{n^{\gamma}}{13}}^{\lceil(1-\frac{1}{e})n\rceil+2}e^{-2mc+m-1+cO\left(\frac{1}{n}\right)}m^{-m}n^{\gamma
m+O\left(\frac{1}{n}\right)}$ (32)
$\displaystyle\leq\sum_{m=\frac{n^{\gamma}}{13}}^{\lceil(1-\frac{1}{e})n\rceil+2}e^{-2mc+m-1+cO\left(\frac{1}{n}\right)}13^{m}n^{O\left(\frac{1}{n}\right)},$
(33)

where (33) follows because $m^{-m}n^{\gamma m}=(\frac{n^{\gamma}}{m})^{m}\leq
13^{m}$. Noting that $n^{O\left(\frac{1}{n}\right)}<2$ for $n$ sufficiently
large, whenever $c>3$, this is less than

$\displaystyle\sum_{m=\frac{n^{\gamma}}{13}}^{\lceil(1-\frac{1}{e})n\rceil+2}2e^{-2mc+(1+\log
13)m-1+cO\left(\frac{1}{n}\right)}<2\sum_{m=\frac{n^{\gamma}}{13}}^{\lceil(1-\frac{1}{e})n\rceil+2}e^{-mc}<2\sum_{m=1}^{\infty}(e^{-mc})<4e^{-c},$

∎

###  5.3 Very small first part ($m>\lceil(1-\frac{1}{e})n\rceil+2$)

Consider $\lambda\vdash n$ with $\lambda_{1}=n-m$ such that
$m>\lceil(1-\frac{1}{e})n\rceil+2$. Applying Proposition 14 and Proposition
15, for all $T\in\operatorname{SYT}(\lambda),$

$\displaystyle\operatorname{eig}(T)<1-\frac{m}{n}+2^{1-k}+\frac{1}{n}<\frac{1}{e}-\frac{2}{n}+2^{1-k}+\frac{1}{n}<\frac{1}{e},$

where we used that $m>(1-\frac{1}{e})n+2$ and allowed $n$ to be sufficiently
large. As $\operatorname{eig}(T)>-\frac{2\log n}{n}$, this implies that
$|\operatorname{eig}(T)|<\frac{1}{e}.$

Thus, taking $t=\frac{1}{2}n\log n+cn,$ we see that

$\displaystyle\sum_{m=(1-\frac{1}{e})n}^{n-1}\left(\sum_{\begin{subarray}{c}\lambda\vdash
n\\\
\lambda_{1}=n-m\end{subarray}}d_{\lambda}\sum_{T\in\operatorname{SYT}(\lambda)}\operatorname{eig}(T)^{2t}\right)\leq
n!\left(\frac{1}{e}\right)^{n\log n+2cn}<e^{-c},$

for $n$ sufficiently large, where the last inequality follows from the bound
$\sum_{\lambda\vdash n}d_{\lambda}^{2}=n!<n^{n}$. This shows (19).

##  6 An $\ell_{2}$ lower bound

In the previous two sections we gave upper bounds for the mixing time of
$P_{n,k}$ by using Equation 2. In this section, we show that these are the
best bounds achievable by this technique.

We consider the contribution of eigenvalues corresponding to tableau of shape
$\lambda=(n-1,1).$ In this section, we will let $T_{i}$ denote the standard
Young tableau of shape $(n-1,1)$ such that $T_{i}(2,1)=i.$ We can find an
exact formula for $\operatorname{eig}(T_{i})$, and by considering only these
eigenvalues, we produce a lower bound on the $\ell^{2}$ distance via

$\left\lVert\frac{P_{n,k}^{t}}{U}-1\right\rVert_{2}^{2}=\sum_{\begin{subarray}{c}\lambda\vdash
n\\\ \lambda\neq(n)\end{subarray}}d_{\lambda}\sum_{\lambda\in
SYT(\lambda)}\operatorname{eig}(T)^{2t}\geq(n-1)\sum_{i=2}^{n}\operatorname{eig}(T_{i}),$
(34)

where we used that $d_{(n-1,1)}=n-1.$ The primary result of this section is
the following:

To calculate these eigenvalues, we only need $\nu(\pi,a)$ in two special
cases. Let $p<n$.

######  Proposition 25.

For a partition $\pi\vdash p$, we have
$\nu(\pi,1)=\left(\frac{\pi_{1}+1}{|\pi|+1}\right)^{k}$.

###### Proof.

Applying Equation 4,

$\displaystyle\nu(\pi,1)=\sum_{u=0}^{k}\nu(\pi,1,u)=\nu(\pi,1,0)=\left(\frac{\pi_{1}+1}{|\pi|+1}\right)^{k},$

where we used Proposition 11 and Proposition 13. ∎

######  Proposition 26.

For a partition $\pi\vdash p$ with $\pi_{2}=0$, we have
$\nu(\pi,2)=\frac{1-(|\pi|+1)^{k-1}}{|\pi|(|\pi|+1)^{k-1}}$.

###### Proof.

When $\pi_{2}=0$ and $a=2,$ recalling the definitions from Definition 8,

$\displaystyle\nu(\pi,2)$
$\displaystyle=\frac{1}{(|\pi|+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\sum_{\tilde{\bm{a}}\in
S_{\ell}(2)}(-1)^{u(\tilde{\bm{a}})}\prod_{1\leq i\leq
a}\pi_{i}^{d_{i}(\tilde{\bm{a}})}$
$\displaystyle=\frac{1}{(|\pi|+1)^{k}}\left[1-\sum_{1\leq\ell\leq
k}\binom{k}{\ell}\pi_{1}^{\ell-1}\right],$

where here we observed that since $\pi_{2}=0,$ when $\ell>0,$ the only choice
of $\tilde{\bm{a}}$ that has non-zero contribution is the tuple
$(2,1,\cdots,1)$. Because $\pi_{1}=|\pi|,$ we have that this is equal to

$\displaystyle\frac{1}{(|\pi|+1)^{k}}\left[1+\frac{1}{|\pi|}-\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\pi_{1}^{\ell-1}\right]$
$\displaystyle=\frac{1}{(|\pi|+1)^{k}}\cdot\frac{|\pi|+1+(|\pi|+1)^{k}}{|\pi|}=\frac{1+(|\pi|+1)^{k-1}}{|\pi|(|\pi|+1)^{k-1}},$

as desired. ∎

We can now directly give the eigenvalue corresponding to $T_{i}$.

######  Proposition 27.

For $T_{i}$ defined above, we have

$\operatorname{eig}(T_{i})=1-\frac{1}{n}\left(\frac{i^{k}-1}{(i-1)i^{k-1}}+\sum_{j=i}^{n-1}\frac{(j+1)^{k}-j^{k}}{(j+1)^{k}}\right).$

###### Proof.

Suppose that the standard Young tableau $T_{i}$ is identified with the
partitions
$\emptyset=\lambda^{(0)},\lambda^{(1)},\cdots,\lambda^{(n)}=(n-1,1),$ as in
(3). Then using Theorem 9,

$\displaystyle\operatorname{eig}(T_{i})$
$\displaystyle=\frac{1}{n}\sum_{j=0}^{n-1}\nu(\lambda^{(j)},a^{(j)})$
$\displaystyle=1-\frac{1}{n}\sum_{j=0}^{n-1}(1-\nu(\lambda^{(j)},a^{(j)}))$
$\displaystyle=1-\frac{1}{n}\sum_{j=0}^{i-2}(1-\nu(\lambda^{(j)},1))-\frac{1}{n}(1-\nu(\lambda^{(i-1)},2))-\frac{1}{n}\sum_{j=i}^{n-1}(1-\nu(\lambda^{(j)},1)),$
(35)

where in the last line we observed that $a^{(j)}\neq 1$ only if $j=i-1,$ when
$a^{(j)}=2.$ Proposition 25 shows that for $1\leq j\leq i-2,$

$1-\nu(\lambda^{(j)},1)=1-\left(\frac{\lambda^{(j)}_{1}+1}{|\lambda^{(j)}|+1}\right)^{k}=1-\left(\frac{j+1}{j+1}\right)^{k}=0$
(36)

and for $i\leq j\leq n-1,$

$1-\nu(\lambda^{(j)},1)=1-\left(\frac{\lambda^{(j)}_{1}+1}{|\lambda^{(j)}|+1}\right)^{k}=1-\left(\frac{j}{j+1}\right)^{k}=\frac{(j+1)^{k}-j^{k}}{(j+1)^{k}}.$
(37)

Furthermore, Proposition 26 shows that

$1-\nu(\lambda^{(i-1)},2)=1-\frac{1-i^{k-1}}{(i-1)i^{k-1}}=\frac{i^{k}-1}{(i-1)i^{k-1}}.$
(38)

The result follows by plugging in (36), (37), and (38) into (35). ∎

######  Corollary 28 (A large universal eigenvalue).

For $i=n$, Proposition 27 gives

$\operatorname{eig}(T_{n})=1-\frac{1}{n}\cdot\frac{n^{k}-1}{(n-1)n^{k-1}}>1-\frac{1}{n+1}.$

We may now prove Theorem 3.

###### Proof of Theorem 3.

Using Equation 34 and Corollary 28, for all $k\geq 1$ and $t=\frac{1}{2}n\log
n+cn,$

$\displaystyle\sum_{\begin{subarray}{c}\lambda\vdash n\\\
\lambda\neq(n)\end{subarray}}d_{\lambda}\sum_{\lambda\in
SYT(\lambda)}\operatorname{eig}(T)^{2t}$
$\displaystyle>(n-1)\operatorname{eig}(T_{n})^{2t}$
$\displaystyle>(n-1)\left(1-\frac{1}{n+1}\right)^{n\log n+2cn}>e^{2c}.$

Now consider the case when $k=n^{\gamma}$. First observe that

$\displaystyle\operatorname{eig}(T_{i})$
$\displaystyle=1-\frac{1}{n}\left(\frac{i^{k}-1}{(i-1)i^{k-1}}+\sum_{j=i}^{n-1}\frac{(j+1)^{k}-j^{k}}{(j+1)^{k}}\right)$
$\displaystyle\geq
1-\frac{1}{n}\left(\frac{i}{i-1}+\sum_{j=i}^{n-1}\frac{k}{j+1}\right).$

When $i\geq n-\frac{n^{1-\gamma}}{\log n}$, $\frac{i}{i-1}=1+o(1),$ and
furthermore,

$\displaystyle\sum_{j=i}^{n-1}\frac{k}{j+1}\leq\frac{n^{1-\gamma}}{\log
n}\left(\frac{n^{\gamma}}{n-\frac{n^{1-\gamma}}{\log n}}\right)=o(1).$

Proceeding from (34), and taking $t=(1-\frac{\gamma}{2})n\log
n-\frac{1}{2}n\log\log n-cn,$

$\displaystyle(n-1)\sum_{i=2}^{n}\operatorname{eig}(T_{i})$
$\displaystyle>(n-1)\sum_{i=n-\frac{n^{1-\gamma}}{\log
n}}^{n}\operatorname{eig}(T_{i})^{2t}$
$\displaystyle\geq(n-1)\frac{n^{1-\gamma}}{\log
n}\left(1-\frac{1}{n}+o\left(\frac{1}{n}\right)\right)^{2t}>e^{2c}.$

∎

##  7 Lower bound

In this section, we give a lower bound for the mixing time of $P_{n,k}$ using
a coupon-collecting argument. Recall that one step of the one-sided
$k-$transposition shuffle involves first selecting a card $r_{i}$ uniformly
from $\\{1,2,\cdots,n\\}$ and then selecting a set of cards $L_{i}$ by
sampling $k$ times uniformly from $\\{1,2,\cdots,r_{i}\\}$ with replacement
(thus, $|L_{i}|\leq k$). Following the strategy in [12] closely, we observe
that intuitively this process is relatively unlikely to choose cards near the
top of the deck. Therefore, we focus on

$V_{n}=\\{n-n/m+1,\cdots,n-1,n\\},$

the set representing the top $n/m$ cards in the deck, where $m=k\log n$.
Further let

$B_{n}:=\\{\rho\in S_{n}:\rho\text{ has at least 1 fixed point in }V_{n}\\}.$

The idea is to use the simple bound

$\left\lVert P_{k,n}^{t}-U\right\rVert_{\operatorname{T.V.}}\geq
P_{n,k}^{t}(B_{n})-U(B_{n}).$ (39)

It is easy to see that $U(B_{n})\leq 1/m\rightarrow 0$ as
$n\rightarrow\infty$. Thus, it suffices to bound $P_{n,k}^{t}(B_{n})$
appropriately. Let $U_{n}^{t}$ be the set of untouched cards in $V_{n}$ after
$t$ iterations of the shuffle. Then

$P_{k,n}^{t}(B_{n})\geq\mathrm{Pr}(|U_{n}^{t}|\geq 1)$

(i.e., the probability that there exists an untouched card in $V_{n}$). Thus,
we have reduced our problem to a variant of coupon collecting. We begin by
modeling what happens in one iteration of the shuffle:

$\displaystyle|V_{n}\setminus U_{n}^{t+1}|-|V_{n}\setminus U_{n}^{t}|$
$\displaystyle=|(\\{r^{t+1}\\}\cup L^{t+1})\cap U_{n}^{t}|$
$\displaystyle\leq\mathds{1}[r^{t+1}\in U_{n}^{t}]+|L^{t+1}\cap U_{n}^{t}|$
$\displaystyle\leq\mathds{1}[r^{t+1}\in U_{n}^{t},|L^{t+1}\cap
U_{n}^{t}|>0]+\mathds{1}[r^{t+1}\in U_{n}^{t},|L^{t+1}\cap
U_{n}^{t}|=0]+|L^{t+1}\cap U_{n}^{t}|$
$\displaystyle\leq\mathds{1}[|L^{t+1}\cap U_{n}^{t}|>0]+|L^{t+1}\cap
U_{n}^{t}|+\mathds{1}[r^{t+1}\in U_{n}^{t},|L^{t+1}\cap U_{n}^{t}|=0].$ (40)

Clearly,

$\mathrm{Pr}(r^{t+1}\in U_{n}^{t},|L^{t+1}\cap
U_{n}^{t}|=0)\leq\mathrm{Pr}(r^{t+1}\in U_{n}^{t})=\frac{|U_{n}^{t}|}{n}.$
(41)

We now focus our attention on the quantity $|L^{t+1}\cap U_{n}^{t}|$.

######  Proposition 29.

Let $s\in[n]$. We have

$\mathrm{Pr}(|L^{t+1}\cap U_{n}^{t}|\geq
s)\leq\frac{1}{m}\left(\frac{k|U_{n}^{t}|}{n-\frac{n}{m}}\right)^{s}.$

###### Proof.

If $r_{t}\leq n-\frac{n}{m},$ then $|L^{t+1}\cap U_{n}^{t}|=0.$ Otherwise, we
can use the naïve bound

$\mathrm{Pr}(l\in U_{n}^{t}|l\in
L^{t+1},r^{t}>n-\frac{n}{m})\leq\frac{|U_{n}^{t}|}{n-\frac{n}{m}},$

which arises by considering the extreme case when $r^{t}=n$. This gives

$\displaystyle\mathrm{Pr}(|L^{t+1}\cap U_{n}^{t}|\geq s)$
$\displaystyle\leq\mathrm{Pr}(r_{t}>n-\frac{n}{m})\cdot\mathrm{Pr}\left[\text{Bin}\left(k,\frac{|U_{n}^{t}|}{n-\frac{n}{m}}\right)\geq
s\right]$
$\displaystyle\leq\frac{1}{m}\left(\frac{k|U_{n}^{t}|}{n-\frac{n}{m}}\right)^{s}.$

∎

We now let $\mathcal{T}_{i}$ be the number of integers $t\geq 0$ for which
$|V_{n}\setminus U_{n}^{t}|=i$. Thus, setting
$\mathcal{T}:=\mathcal{T}_{0}+\mathcal{T}_{1}+\cdots+\mathcal{T}_{\frac{n}{m}-1}$
to be the time it takes to collect all cards in $V_{n}$,

$\mathrm{Pr}(|U_{n}|^{t}\geq 1)=\mathrm{Pr}(\mathcal{T}>t).$ (42)

Let $S_{i,j}$ be the event that we go from having exactly $j$ collected cards
straight to having more than $i$ collected cards. Then

$\displaystyle\mathrm{Pr}(S_{i,j})\leq\frac{\mathrm{Pr}(|L^{t+1}\cap
U_{n}^{t}|\geq
i-j)}{\mathrm{Pr}(U_{n}^{t+1}<U_{n}^{t})}\leq\frac{\frac{1}{m}\left(\frac{k|U_{n}^{t}|}{n-n/m}\right)^{i-j}}{|U_{n}^{t}|/n},$

where we applied Proposition 29 and bounded the denominator from below by
$\mathrm{Pr}(r^{t+1}\in U_{n}^{t})=\frac{|U_{n}^{t}|}{n}$. Thus,

$\displaystyle\mathrm{Pr}(\mathcal{T}_{i}=0)$
$\displaystyle\leq\sum_{j=i-k}^{i-1}\mathrm{Pr}(S_{i,j})<\sum_{s=1}^{k}\frac{\frac{1}{m}\left(\frac{k|U_{n}^{t}|}{n-n/m}\right)^{s}}{|U_{n}^{t}|/n}\leq
1.1\sum_{s=1}^{k}\frac{k}{m}\left(\frac{k|U_{n}^{t}|}{n-\frac{n}{m}}\right)^{s-1}<\frac{2k}{m},$

where the last inequality follows easily because
$\frac{k|U_{n}^{t}|}{n-n/m}\leq\frac{kn/m}{n-n/m}=\frac{1}{(1-1/m)\log
n}<\frac{1}{3},$ since $m=k\log n$. Then $\mathcal{T}_{i}$ stochastically
dominates $\mathcal{T}_{i}^{\prime}$ given by

$\displaystyle\mathrm{Pr}(\mathcal{T}_{i}^{\prime}=j)=\begin{cases}2k/m,&j=0\\\
(1-2k/m)p_{i}(1-p_{i})^{j-1},&j\geq 1,\end{cases}$

where

$\displaystyle p_{i}$
$\displaystyle:=\mathrm{Pr}(|U_{n}^{t+1}|<|U_{n}^{t}|:|U_{n}^{t}|=\frac{n}{m}-i)$
$\displaystyle\leq\mathrm{Pr}(|L^{t+1}\cap U_{n}^{t}|\geq
1)+\mathrm{Pr}(r^{t+1}\in U_{n}^{t})$ (43)
$\displaystyle\leq\frac{1}{m}\left(\frac{k(\frac{n}{m}-i)}{n-\frac{n}{m}}\right)+\frac{\frac{n}{m}-i}{n}=\frac{k+m-1}{(m-1)n}\left(\frac{n}{m}-i\right),$
(44)

where (43) is a consequence of (40), and (44) follows by applying Proposition
29 and (41) and then simplifying.

We may now apply Chebyshev’s inequality to
$\mathcal{T}^{\prime}=\mathcal{T}_{0}^{\prime}+\mathcal{T}_{1}^{\prime}+\cdots+\mathcal{T}_{\frac{n}{m}-1}^{\prime}$.
Recalling that $m=k\log n,$

$\displaystyle\operatorname{E}[\mathcal{T}^{\prime}]=\sum_{i=0}^{\frac{n}{m}-1}\frac{m-2k}{mp_{i}}$
$\displaystyle\geq\frac{m-2k}{m}\cdot\frac{m-1}{k+m-1}\cdot
n\sum_{i=0}^{\frac{n}{m}-1}\frac{1}{\frac{n}{m}-i}$
$\displaystyle\geq\left(1-\frac{4}{\log
n}\right)\cdot\left(n\log\left(\frac{n}{k}\right)-n\log\log n\right)$
$\displaystyle\geq n\log\left(\frac{n}{k}\right)-n\log\log n-4n$

and

$\operatorname{Var}[\mathcal{T}^{\prime}]\leq\sum_{i=0}^{\frac{n}{m}-1}\frac{1}{p_{i}^{2}}\leq\sum_{i=1}^{\frac{n}{m}}\frac{n^{2}}{i^{2}}\leq\frac{\pi^{2}}{6}n^{2},$

where we use that $p_{i}\geq\frac{n/m-i}{n}.$ Thus, for
$t=n\log\left(\frac{n}{k}\right)-n\log\log n-cn,$

$\mathrm{Pr}(\mathcal{T}^{\prime}\leq t)\leq\frac{\pi^{2}}{6(c-4)^{2}}.$

This implies, using Equation 42, that

$\mathrm{Pr}(|U_{n}|^{t}\geq 1)=\mathrm{Pr}(\mathcal{T}>t)\geq
1-\frac{\pi^{2}}{6(c-4)^{2}},$

as desired.

##  8 The case where $k$ is big

In this section, we prove Theorem 5. In particular, if $k=\Omega(n\log n)$,
then $P_{n,k}$ mixes in $O(n)$ steps without cutoff. The proof is simple. We
will show that the mixing time is at most order $n$ using a coupling argument.

Let $t_{\textup{rel}}=(1-\beta)^{-1}$, where $\beta$ is the second largest
eigenvalue of $P_{n,k}$. Then Corollary 28 gives that
$t_{\textup{rel}}=\Omega(n)$. Thus, as a consequence,

$\lim_{n\rightarrow\infty}\frac{t_{\textup{mix}}(\varepsilon)}{t_{\textup{rel}}}\neq\infty,$

which implies that in this regime, there is no cutoff (see, e.g., Proposition
18.4 of [21]).

###### Proof of Theorem 5.

Let $Q$ be the transition matrix of star transpositions. Diaconis [9] proved
that there is a universal, positive constant $A$ such that

$\|Q^{t}_{x}-U\|_{\operatorname{T.V.}}\leq Ae^{-c},$

where $t=n\log n+cn$ with $c>1$. Combining this with the fact that there is a
coupling time $\tau$ such that

$\|Q^{t}_{x}-U\|_{\operatorname{T.V.}}=\mathbb{P}\\!\left(\tau>t\right)$

for every $x\in S_{n}$ (see Proposition 4.7 of [21] for a reference), we get
that

$\mathbb{P}\\!\left(\tau>n\log n+cn\right)<Ae^{-c},$ (45)

if $c>1$. We define the following coupling time $T$ for the one-sided
$k$-transposition shuffle.

Let $X_{t}$ and $Y_{t}$ be two copies of the one-sided $k$-transposition
shuffle. We recall that one step of the one-sided transposition shuffle
consists of choosing $j\in\\{1,\cdots,n\\}$, choosing
$i_{1},\cdots,i_{k}\in\\{1,\cdots,j\\},$ and then applying the permutation
$(j;i_{1},\ldots,i_{k})$. Then a coupling is given as follows: For $1\leq
j\leq n-1$ we apply the same permutation $(j;i_{1},\ldots,i_{k})$ to both
chains. That is

$X_{t+1}=X_{t}(j;i_{1},\ldots,i_{k})\mbox{ and
}Y_{t+1}=Y_{t}(j;i_{1},\ldots,i_{k}).$

When $j=n,$ the permutation applied is equivalent to $k$ star transpositions.
In this case, we couple $X_{t}$ and $Y_{t}$ according to the star
transpositions coupling.

Let $T$ be the first time that $X_{t}=Y_{t}$. The standard coupling inequality
says

$d_{n,k}(t)\leq\mathbb{P}\\!\left(T>t\right).$

Roughly speaking, the coupling progresses whenever $j=n$, so it suffices to
consider how often this happens. Let $B$ be a Binomial$(t,1/n)$ random
variable counting the number of times before time $t+1$ that $j=n$. Then,

$\mathbb{P}\\!\left(T>t\right)\leq\mathbb{P}\\!\left(T>t\bigg{|}B>\frac{t}{2n}\right)+\mathbb{P}\\!\left(B\leq\frac{t}{2n}\right).$

We start with the case $k=\Omega(n\log n)$. For $t=4dn$ with $d>\frac{n\log
n}{k}$, we have that

$\mathbb{P}\\!\left(T>t\right)\leq\mathbb{P}\\!\left(\tau>2dk\right)+e^{-2d}\leq\mathbb{P}\\!\left(\tau>2n\log
n\right)+e^{-2d},$ (46)

where we observed that $B>\frac{t}{2n}$ implies we have applied $2dk$ star
transpositions, and bounded the tail of the binomial distribution. Combining
equations (45) and (46), we get that there are positive constants $A,B$ that
are universal on $n$ such that

$d_{n,k}(t)\leq Ae^{-Bd},$

where $t=4dn$. For $k\in[n,n\log n]$ the same argument holds for
$t=O\left(\frac{n^{2}\log n}{k}\right)$.

We now present the lower bound. Equation (12.15) of [21] says that for every
eigenvalue $\beta\neq 1$ of $P_{n,k}$ we have that

$|\beta|^{t}\leq 2\left\lVert
P_{n,k}^{t}-U\right\rVert_{\operatorname{T.V.}}.$

Using Corollary 28 we have that

$\left(1-\frac{1}{n+1}\right)^{t}\leq|\operatorname{eig}(T_{n})|^{t}\leq
2\left\lVert P_{n,k}^{t}-U\right\rVert_{\operatorname{T.V.}},$

which shows that $t_{\text{mix}}(\varepsilon)=\Omega(n)$ for every $k$.

∎

## Appendix: Lifting Eigenvectors

In this section, we will prove Theorem 7 and Theorem 9, which together give
the eigenvalues of $P_{n,k}$. Our approach closely follows that of [12], who
in turn closely follows the approach of [1]. In brief, the strategy is to
recursively find the eigenvectors of $P_{n+1,k}$ in terms of those of
$P_{n,k}$ by considering the group algebra $\SS_{n}=\mathbb{C}[S_{n}]$ and its
representations. We now introduce some background, following the outline of
[12] closely.

Let $[n]=\\{1,2,\cdots,n\\}$ for $n\in\mathbb{N}.$ Given $n\in\mathbb{N},$
allow $W^{n}$ to be the set of words $w=w_{1}\cdot w_{2}\cdot\ldots\cdot
w_{n}$ of length $n$ with elements $w_{i}\in[n].$ We let $S_{n}$ act on
$W^{n}$ via place permutations, i.e., for $\sigma\in S_{n},$
$\sigma(w_{1}\cdot w_{2}\cdot\ldots\cdot w_{n}):=w_{\sigma^{-1}(1)}\cdot
w_{\sigma^{-1}(2)}\cdot\ldots\cdot w_{\sigma^{-1}(n)}.$ Now let $M^{n}$ be the
vector space over $\mathbb{C}$ with basis $W^{n},$ on which the $S^{n}-$action
we define above extends to.

For $w\in W^{n}$, let $\operatorname{eval}_{i}(w)$ be the number of
occurrences of $i$ in the word $w$. Then define
$\operatorname{eval}(w):=(\operatorname{eval}_{1}(w),\cdots,\operatorname{eval}_{n}(w))$
be the evaluation of $w$. If $\operatorname{eval}(w)$ is non-increasing, then
we identify $\operatorname{eval}(w)$ with a partition $\lambda\vdash n$ where
$\lambda_{1}=\operatorname{eval}_{1}(w),\lambda_{2}=\operatorname{eval}_{2}(w),\cdots.$
Furthermore, to any standard Young tableau $T$ of shape $\lambda\vdash n$ we
may associate a word $w=w_{1}\cdot w_{2}\cdot\ldots\cdot w_{n}\in W^{n},$
where $w_{T(i,j)}=i$ for all boxes $(i,j)$ in $T$. Two tableaux are associated
with the same word if and only if they have both the same shape and the same
values in each row.

######  Definition 30.

Given $\lambda\vdash n,$ we can associate to it a simple module $S^{\lambda}$
of $\SS_{n}$ called the Specht module for $\lambda$. It has dimension
$d_{\lambda}:=\operatorname{SYT}(T)$.

######  Definition 31.

Given $\lambda\vdash n$, define $M^{\lambda}$ to be the span of $\\{w\in
W^{n}:\operatorname{eval}(w)=\lambda\\}.$ This is clearly a
$\SS_{n}$-submodule of $M^{n}$.

We are now ready to see how this relates to card shuffles. Let
$(1^{n}):=(1,\cdots,1)$ denote the partition of all ones. Then $M^{(1^{n})}$
is spanned by the $n!$ permutations of the word $1\cdot 2\cdot\ldots\cdot n\in
W^{n}$; thus, card shuffles can be studied as linear operators on
$M^{(1^{n})}$.

Indeed, consider the one-sided $k-$transposition shuffle on $n$ cards as the
following element of the group algebra $\SS_{n}$:

$\sum_{1\leq j\leq n}\sum_{1\leq i_{1},\cdots,i_{k}\leq
j}P_{n,k}((j;i_{1},\cdots,i_{k}))(j;i_{1},\cdots,i_{k})=\sum_{1\leq j\leq
n}\sum_{1\leq i_{1},\cdots,i_{k}\leq
j}\frac{1}{nj^{k}}(j;i_{1},\cdots,i_{k}).$

To simplify our calculations, we scale this operator by $n$ to get the
operator

$Q_{n,k}:=\sum_{1\leq j\leq n}\sum_{1\leq i_{1},\cdots,i_{k}\leq
j}\frac{1}{j^{k}}(j;i_{1},\cdots,i_{k}).$

We seek to determine the eigenvalues of $Q_{n,k}$ on $M^{(1^{n})}.$ The
following standard results indicate that it suffices to find the eigenvalues
of $Q_{n,k}$ on $S^{\lambda}$, and that we may study the action of $Q_{n,k}$
on $S^{\lambda}$ within the module $M^{\lambda}.$

######  Lemma 32.

Given $\lambda\vdash n,$

$M^{\lambda}\cong\bigoplus_{\mu\trianglerighteq\lambda}K_{\lambda,\mu}S^{\mu},$

where $K_{\lambda,\lambda}=1$ and $K_{\lambda,\mu}$ are the Kostka numbers. In
particular,

$M^{(1^{n})}\cong\bigoplus_{\lambda\vdash n}d_{\lambda}S^{\lambda}.$

The following key operators will allow us to connect $Q_{n+1,k}$ with
$Q_{n,k}.$

######  Definition 33.

For $a\in[n+1],$ define the adding operator $\Phi_{a}:M^{n}\rightarrow
M^{n+1}$ so that for $w\in W^{n}$,

$\Phi_{a}(w):=w\cdot a.$

In other words, $\Phi_{a}$ appends the symbol $a$ to the end of the word $w$.

Furthermore, for $a,b\in[n],$ define the switching operator
$\Theta_{b,a}:M^{n}\rightarrow M^{n}$ so that for $w=w_{1}\cdot
w_{2}\cdot\ldots\cdot w_{n}\in W^{n},$

$\Theta_{b,a}(w):=\sum_{\begin{subarray}{c}1\leq i\leq n\\\
w_{i}=b\end{subarray}}w_{1}\cdot\ldots\cdot w_{i-1}\cdot a\cdot
w_{i+1}\cdot\ldots\cdot w_{n}.$

In other words, $\Theta_{b,a}$ sums all words formed by replacing an
occurrence of the symbol $a$ in $w$ with the symbol $b$.

The operators defined above behave nicely when restricted to the modules
$M^{\lambda}.$ The following definition will be useful in this case.

######  Definition 34.

Given an $n-$tuple $\lambda=(\lambda_{1},\cdots,\lambda_{n})$ of non-negative
integers summing to $n$, we define $\lambda+e_{a}$ to be the $(n+1)-$tuple
$(\lambda_{1},\cdots,\lambda_{n},0)+(0,\cdots,0,1)$ of non-negative integers
summing to $n+1.$

######  Lemma 35 (Lemma 31 in [12]).

For $a\in[n+1]$ and an $n-$tuple $\lambda$ of non-negative integers summing to
$n$,

$\Phi_{a}:M^{\lambda}\rightarrow M^{\lambda+e_{a}},$

and that for $a,b\in[n],$ and $n-$tuples $\lambda,\mu$ of non-negative
integers summing to $n$ where $\lambda+e_{a}=\mu+e_{b},$

$\Phi_{b,a}:M^{\lambda}\rightarrow M^{\mu}.$

We are now ready to show a key result illustrating the recursive structure of
$Q_{n,k}.$

######  Proposition 36.

$Q_{n+1,k}\circ\Phi_{a}-\Phi_{a}\circ
Q_{n,k}=\frac{1}{(n+1)^{k}}\sum_{0\leq\ell\leq k}\binom{k}{\ell}\sum_{1\leq
x_{1},\cdots,x_{\ell}\leq
n}\Phi_{x_{\ell}}\circ\Theta_{x_{\ell},x_{\ell-1}}\circ\cdots\circ\Theta_{x_{2},x_{1}}\circ\Theta_{x_{1},a}$
(47)

###### Proof.

Begin by observing that for $w\in W^{n},$ we can expand
$(Q_{n+1,k}\circ\Phi_{a})(w)$ as

$\displaystyle\,\sum_{1\leq i_{1},\cdots,i_{k}\leq
n+1}\frac{1}{(n+1)^{k}}(n+1;i_{1},\cdots,i_{k})(w\cdot a)+\sum_{1\leq j\leq
n}\sum_{1\leq i_{1},\cdots,i_{k}\leq
j}\frac{1}{j^{k}}(j;i_{1},\cdots,i_{k})(w\cdot a)$ $\displaystyle=$
$\displaystyle\sum_{1\leq i_{1},\cdots,i_{k}\leq
n+1}\frac{1}{(n+1)^{k}}(n+1;i_{1},\cdots,i_{k})(w\cdot a)+\sum_{1\leq j\leq
n}\sum_{1\leq i_{1},\cdots,i_{k}\leq
j}\frac{1}{j^{k}}\Phi_{a}((j;i_{1},\cdots,i_{k})(w))$ $\displaystyle=$
$\displaystyle\sum_{1\leq i_{1},\cdots,i_{k}\leq
n+1}\frac{1}{(n+1)^{k}}(n+1;i_{1},\cdots,i_{k})(w\cdot a)+(\Phi_{a}\circ
Q_{n,k})(w),$

where the primary observation is that we may freely interchange the order of
adding a card at the $(n+1)$-th position and permuting the first $n$ cards.
Thus,

$(Q_{n+1,k}\circ\Phi_{a}-\Phi_{a}\circ
Q_{n,k})(w)=\frac{1}{(n+1)^{k}}\sum_{1\leq i_{1},\cdots,i_{k}\leq
n+1}(n+1;i_{1},\cdots,i_{k})(w\cdot a),$

so it suffices to show that

$\sum_{1\leq i_{1},\cdots,i_{k}\leq n+1}(n+1;i_{1},\cdots,i_{k})(w\cdot
a)=\sum_{0\leq\ell\leq k}\binom{k}{\ell}\sum_{1\leq x_{1},\cdots,x_{\ell}\leq
n}\Phi_{x_{\ell}}\circ\Theta_{x_{\ell},x_{\ell-1}}\circ\cdots\circ\Theta_{x_{2},x_{1}}\circ\Theta_{x_{1},a}.$

First notice the identity

$\sum_{1\leq i_{1},\cdots,i_{k}\leq n+1}(n+1;i_{1},\cdots,i_{k})(w\cdot
a)=\sum_{0\leq\ell\leq k}\binom{k}{\ell}\sum_{1\leq
i_{1}^{\prime},\cdots,i_{\ell}^{\prime}\leq
n}(n+1;i_{1}^{\prime},\cdots,i_{\ell}^{\prime})(w\cdot a),$

which becomes clear when viewing $\ell$ as the number of elements among
$i_{1},\cdots,i_{k}$ that are not equal to $n+1.$ Finally, note that

$\sum_{1\leq i_{1}^{\prime},\cdots,i_{\ell}^{\prime}\leq
n}(n+1;i_{1}^{\prime},\cdots,i_{\ell}^{\prime})(w\cdot a)=\sum_{1\leq
x_{1},\cdots,x_{\ell}\leq
n}\Phi_{x_{\ell}}\circ\Theta_{x_{\ell},x_{\ell-1}}\circ\cdots\circ\Theta_{x_{2},x_{1}}\circ\Theta_{x_{1},a},$

as both sides of the equation represent adding the symbol $a$ at the end of
the word, and considering the results of all possible combinations of $\ell$
transpositions with this position. ∎

######  Corollary 37.

$(Q_{n+1,k}\circ\Phi_{a}-\Phi_{a}\circ
Q_{n,k})|_{S^{\lambda}}=\frac{1}{(n+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\sum_{(a,x_{1},\cdots,x_{\ell})\in
S_{\ell}(a)}\Phi_{x_{\ell}}\circ\Theta_{x_{\ell},x_{\ell-1}}\circ\cdots\circ\Theta_{x_{2},x_{1}}\circ\Theta_{x_{1},a}|_{S^{\lambda}}$
(48)

where we recall the definition
$S_{\ell}(a):=\\{(a,x_{1},\cdots,x_{\ell})\in\mathbb{Z}^{\ell+1}:a\geq
x_{1}\geq\cdots\geq x_{\ell}\geq 1\\}.$

###### Proof.

This is an immediate consequence of the following fact, which is proven as
Lemma 34 in [12]: For $\lambda,\mu\vdash n$ such that
$\lambda+e_{a}=\mu+e_{b}$ for some $a,b\in[n],$ then $\Theta_{b,a}$ is non-
zero on $S^{\lambda}$ if and only if $\lambda$ dominates $\mu$. Thus, if
$a<b,$ then $\Theta_{b,a}(S^{\lambda})=0.$ ∎

The final key component of our proof involves defining the lifting operators,
which map eigenvectors of $Q_{n,k}$ to eigenvectors of $Q_{n+1,k}.$ First, we
give a useful lemma characterizing the image of the adding operators
$\Phi_{a}.$

######  Lemma 38 (Lemma 36 in [12]).

Consider $\lambda\vdash n$ and $\lambda+e_{a}\vdash n+1$. Then
$\Phi_{a}(S^{\lambda})$ is contained in an $\SS_{n+1}-$submodule of
$M^{\lambda+e_{a}}$ isomorphic to $\bigoplus_{\mu}S^{\mu}$, where the sum
ranges over partitions $\mu$ that can be obtained from $\lambda$ by adding a
box in row $i$ for $i\leq a.$

######  Definition 39.

We will define $\pi^{\mu}:V\rightarrow V$ to be the isotypic projection that
projects onto the $S^{\mu}-$component of $V$. Furthermore, for $\lambda\vdash
n,\mu\vdash n+1$, define the operators

$\kappa_{b}^{\lambda,\mu}:=\pi^{\mu}\circ\Phi_{b}:S^{\lambda}\rightarrow\Phi_{b}(S^{\lambda}).$

As a particular case, define the lifting operators

$\kappa_{a}^{\lambda,\lambda+e_{a}}:S^{\lambda}\rightarrow S^{\lambda+e_{a}},$

where the image of $\kappa_{a}^{\lambda,\lambda+e_{a}}$ is clear because
$\Phi_{a}(\lambda)$ has a unique $S^{\lambda+e_{a}}$ component (Lemma 38).

We are particularly interested in the lifting operators
$\kappa_{a}^{\lambda,\lambda+e_{a}},$ as these will allow us to “lift” the
eigenvectors of $Q_{n,k}$ to $Q_{n+1,k}.$ A key result is that these operators
are injective, and thus do not lose any eigenvectors.

######  Lemma 40 (Lemma 39 in [12]).

Consider $\lambda\vdash n$ where $\lambda+e_{a}\vdash n+1$. Then the linear
operator $\kappa_{a}^{\lambda,\lambda+e_{a}}$ is an injective $\SS_{n}-$module
morphism.

The next two results work towards Theorem 43, which shows how these lifting
operators reveal the recursive structure of the shuffle’s eigenvalues.

######  Lemma 41.

Suppose that $\mu=\lambda+e_{a}$ and let
$a>x^{\prime}_{1}>\cdots>x^{\prime}_{m}\geq 1$. Then

$\pi^{\mu}\circ\Phi_{x^{\prime}_{m}}\circ\Theta_{x^{\prime}_{m},x^{\prime}_{m-1}},\cdots,\Theta_{x^{\prime}_{2},x^{\prime}_{1}},\Theta_{x^{\prime}_{1},a}=(-1)^{m}\kappa_{a}^{\lambda,\mu}.$
(49)

###### Proof.

The proof follows from repeated application of the following two facts: First,
that

$\Phi_{b}\circ\Theta_{b,a}=\Theta_{b,a}\circ\Phi_{b}-\Phi_{a},$

and second, that for $a>b>c,$

$\Phi_{c}\circ\Theta_{b,a}=\Theta_{b,a}\circ\Phi_{c}.$

Both of these facts are easily seen from the definitions of the adding and
switching operators. This gives that the left hand side above is equal to

$(-1)^{m}\kappa_{a}+\sum_{i=0}^{m-1}(-1)^{i}\Theta_{x^{\prime}_{m-i},x^{\prime}_{m-i-1}}\circ\cdots\circ\Theta_{x^{\prime}_{1},a}\circ\kappa_{x^{\prime}_{m-i}}.$

The result follows from the observation that
$\kappa_{b}^{\lambda,\lambda+e_{a}}=0$ whenever $b<a$ (note that from Lemma
38, we know that $\Phi_{b}(S^{\lambda})$ does not contain an
$S^{\lambda+e_{a}}$ component). ∎

######  Lemma 42.

Suppose that $\mu=\lambda+e_{a}$. Then for
$\tilde{\bm{a}}=(a,x_{1},\cdots,x_{\ell})\in S_{\ell}(a),$

$\pi^{\mu}\circ\Phi_{x_{\ell}}\circ\Theta_{x_{\ell},x_{\ell-1}}\circ\cdots\circ\Theta_{x_{2},x_{1}}\circ\Theta_{x_{1},r}=\left((-1)^{u(\tilde{\bm{a}})}\prod_{1\leq
i\leq a}\lambda_{i}^{d_{i}(\tilde{\bm{a}})}\right)\kappa_{a}^{\lambda,\mu},$
(50)

where we recall that $u(\tilde{\bm{a}})$ is defined as the number of distinct
elements in $\tilde{\bm{a}}$ not equal to $a$, and that
$d_{i}(\tilde{\bm{a}})$ is defined as one fewer than the number of occurrences
of $i$ in $\tilde{\bm{a}}.$

###### Proof.

First observe that $\Theta_{i,i}(w)=\lambda_{i}w,$ i.e., $w$ multiplied by the
number of occurrences of $i$ in $w$. Then we can equate the left hand side to

$\left(\prod_{1\leq i\leq
a}\lambda_{i}^{d_{i}(\tilde{\bm{a}})}\right)\pi^{\mu}\circ\Phi_{x^{\prime}_{u(\tilde{\bm{a}})}}\circ\Theta_{x^{\prime}_{u(\tilde{\bm{a}})},x^{\prime}_{u(\tilde{\bm{a}})-1}},\cdots,\Theta_{x^{\prime}_{2},x^{\prime}_{1}},\Theta_{x^{\prime}_{1},a},$

where $a>x^{\prime}_{1}>\cdots>x^{\prime}_{u(\tilde{\bm{a}})}$ are the unique
values among $a\geq x_{1}\geq\cdots\geq x_{\ell}.$ The result then follows
immediately from Lemma 41. ∎

######  Theorem 43.

For $\lambda\vdash n,a\in[l(\lambda)+1]$ and $\lambda+e_{a}\vdash n+1,$

$Q_{n+1,k}\circ\kappa_{a}^{\lambda,\lambda+e_{a}}-\kappa_{a}^{\lambda,\lambda+e_{a}}\circ
Q_{n,k}=\nu(\lambda,a)\kappa_{a}^{\lambda,\lambda+e_{a}},$ (51)

where we recall that

$\nu(\lambda,a):=\frac{1}{(n+1)^{k}}\sum_{0\leq\ell\leq
k}\binom{k}{\ell}\sum_{\tilde{\bm{a}}\in
S_{\ell}(a)}(-1)^{u(\tilde{\bm{a}})}\prod_{1\leq i\leq
a}\lambda_{i}^{d_{i}(\tilde{\bm{a}})}.$

In particular, if $v\in S^{\lambda}$ is an eigenvector of $Q_{n,k}$ with
eigenvalue $\epsilon$, then $\kappa_{a}^{\lambda,\lambda+e_{a}}(v)$ is an
eigenvector of $Q_{n+1,k}$ with eigenvalue

$\epsilon+\nu(\lambda,a).$

###### Proof.

Observe that

$\pi^{\lambda+e_{a}}\circ(Q_{n+1,k}\circ\Phi_{a}-\Phi_{a}\circ
Q_{n,k})|_{S^{\lambda}}=Q_{n+1,k}\circ\kappa_{a}^{\lambda,\lambda+e_{a}}-\kappa_{a}^{\lambda,\lambda+e_{a}}\circ
Q_{n,k},$

as $\pi^{\lambda}$ (an $\SS_{n+1}-$module morphism) commutes with $Q_{n+1,k}.$
Then (51) is a direct consequence of applying Lemma 42 to the right hand side
of (48). The fact that for an eigenvector $v$ of $Q_{n+1,k}$,
$\kappa_{a}^{\lambda,\lambda+e_{a}}(v)$ is an eigenvector of $Q_{n+1,k}$ with
eigenvalue $\epsilon+\nu(\lambda,a)$ follows after noting that
$\kappa_{a}^{\lambda,\lambda+e_{a}}(v)\neq 0$ since
$\kappa_{a}^{\lambda,\lambda+e_{a}}$ is injective (Lemma 40). ∎

#### Proofs of Theorem 7 and Theorem 9.

We now prove Theorem 7 and Theorem 9 in conjunction. We do this by explicitly
finding the eigenvalues of $Q_{n,k},$ indexed by the standard Young tableau of
size $n$.

We now show how the eigenvalues of $Q_{n+1,k}$ are obtained from those of
$Q_{n,k}$. For $\mu\vdash n+1,$ the branching rules of $S_{n}$ tell us that

$\operatorname{Res}_{\SS_{n}}^{\SS_{n+1}}(S^{\mu})=\bigoplus_{\begin{subarray}{c}\lambda\vdash
n\\\ \lambda\subset\mu\end{subarray}}S^{\lambda}.$

Now for any $\lambda\vdash n$ such that $\lambda\subset\mu,$ there is some $a$
for which $\lambda+e_{a}=\mu.$ From Lemma 40,
$\kappa_{a}^{\lambda,\lambda+e_{a}}$ “lifts” a basis of eigenvectors of
$S^{\lambda}$ to a basis of eigenvectors of $S^{\lambda}$ in
$\operatorname{Res}_{\SS_{n}}^{\SS_{n+1}}(S^{\mu})$. As
$\operatorname{Res}_{\SS_{n}}^{\SS_{n+1}}(S^{\mu})$ is equal to $S^{\mu}$ as a
vector space, we can find a basis of $S^{\mu}$ by lifting eigenvectors of
$S^{\lambda}$ for all $\lambda\vdash n$ such that $\lambda\subset\mu.$

This shows how to recursively construct the eigenvalues of $Q_{n,k}.$ First
observe that $Q_{1,k}$ has the single eigenvalue $1=\nu(\emptyset,1)$
corresponding to $S^{(1)},$ which is of dimension $1$. Then for $\lambda\vdash
n,$ each eigenvalue of $Q_{n,k}$ in $S^{\lambda}$ corresponds to a sequence of
partitions
$\emptyset=\lambda^{(0)},\lambda^{(1)},\cdots,\lambda^{(n)}=\lambda,$ where
$\lambda^{(i+1)}$ is obtained from $\lambda^{(i)}$ by adding one box to row
$a^{(i)}.$ The resulting eigenvalue, by repeated application of Theorem 43, is
equal to

$\sum_{i=0}^{n-1}\nu(\lambda^{(i)},a^{(i)}).$ (52)

Moreover, any such sequence of partitions identifies a standard Young tableau
$T$ of shape $\lambda$. Recalling that
$M^{(1^{n})}\cong\bigoplus_{\lambda\vdash n}d_{\lambda}S^{\lambda},$ we have
that each standard Young tableau $T$ of size $n$ indexes an eigenvalue of
$Q_{n,k}$ of multiplicity $d_{\lambda}$, proving Theorem 7. Finally, Theorem 9
follows from (52) since the eigenvalues of $P_{n,k}$ are exactly $\frac{1}{n}$
times the eigenvalues of $Q_{n,k}$.

## References

  * [1] A.B. Dieker and F.V. Saliola.  Spectral analysis of random-to-random markov chains.  Advances in Mathematics, 323:427–485, 2018.
  * [2] Persi Diaconis and Mehrdad Shahshahani.  Generating a random permutation with random transpositions.  Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 57:159–179, 1981.
  * [3] Bob Hough.  The random $k$ cycle walk on the symmetric group.  Probab. Theory Related Fields, 165(1-2):447–482, 2016.
  * [4] Bob Hough and Yunjiang Jiang.  Cut-off phenomenon in the uniform plane Kac walk.  Ann. Probab., 45(4):2248–2308, 2017.
  * [5] Martin Hildebrand.  Generating random elements in ${\rm SL}_{n}({\bf F}_{q})$ by random transvections.  J. Algebraic Combin., 1(2):133–150, 1992.
  * [6] Evita Nestoridi and Oanh Nguyen.  On the mixing time of the Diaconis-Gangolli random walk on contingency tables over $\mathbb{Z}/q\mathbb{Z}$.  Ann. Inst. Henri Poincaré Probab. Stat., 56(2):983–1001, 2020\.
  * [7] Jeffrey S. Rosenthal.  Random rotations: characters and random walks on ${\rm SO}(N)$.  Ann. Probab., 22(1):398–423, 1994.
  * [8] L. Flatto, A. M. Odlyzko, and D. B. Wales.  Random shuffles and group representations.  Ann. Probab., 13(1):154–178, 1985.
  * [9] Persi Diaconis.  Applications of noncommutative Fourier analysis to probability problems.  In École d’Été de Probabilités de Saint-Flour XV–XVII, 1985–87, volume 1362 of Lecture Notes in Math., pages 51–100. Springer, Berlin, 1988.
  * [10] Megan Bernstein and Evita Nestoridi.  Cutoff for random to random card shuffle.  Ann. Probab., 47(5):3303–3320, 2019.
  * [11] Eliran Subag.  A lower bound for the mixing time of the random-to-random insertions shuffle.  Electron. J. Probab., 18:no. 20, 20, 2013.
  * [12] Michael E. Bate, Stephen B. Connor, and Oliver Matheau-Raven.  Cutoff for a one-sided transposition shuffle.  Ann. Appl. Probab., 31(4):1746–1773, 2021.
  * [13] Justin Salez.  Cutoff for non-negatively curved Markov chains.  arXiv:2102.05597, 2021.
  * [14] Nathanaël Berestycki, Oded Schramm, and Ofer Zeitouni.  Mixing times for random $k$-cycles and coalescence-fragmentation chains.  Ann. Probab., 39(5):1815–1843, 2011.
  * [15] Dave Bayer and Persi Diaconis.  Trailing the dovetail shuffle to its lair.  Ann. Appl. Probab., 2(2):294–313, 1992.
  * [16] Alexey Bufetov and Peter Nejjar.  Cutoff profile of ASEP on a segment.  arXiv:2012.14924, 2020.
  * [17] Eyal Lubetzky and Yuval Peres.  Cutoff on all Ramanujan graphs.  Geom. Funct. Anal., 26(4):1190–1216, 2016.
  * [18] Evita Nestoridi.  The limit profile for star transpositions.  arXiv:2111.03622, 2021.
  * [19] Evita Nestoridi and Sam Olesker-Taylor.  Limit profiles for reversible Markov chains.  Probability Theorey and Related fields, to appear.
  * [20] Lucas Teyssier.  Limit profile for random transpositions.  Ann. Probab., 48(5):2323–2343, 2020.
  * [21] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.  Markov chains and mixing times.  2008\.

††footnotetext:  ∗ Princeton University, United States. E-Mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
. The first author is supported by the NSF Grant DMS-$2052659$.