$\newcommand{\Cat}{{\rm Cat}}$ $\newcommand{\A}{\mathcal A}$ $\newcommand{\freestar}{ \framebox[7pt]{\star} }$

## 5. Chains on $S_n$

1. ### Cutoff for random-to-random shuffle

#### Conjecture 5.1.

[Evita Nestoridi] The random-to-random card shuffle on $S_n$ has cutoff at $\frac {3n}4 \log n$.
The known lower bound is, for any $\epsilon>0$, $(\frac 34-\epsilon)n\log n$ due to Subak and the known upper bounds are $2n\log n$ [Saloff-Coste, Zaniga] improved to $\frac 32 n\log n$ [Morris].

In separation distance there is an $n\log n$ upper bound [Nesterodi, White].
• ### Random biased transpositions

The random uniform transposition walk on $S_n$ is the discrete time Markov chain that at each time step applies a transposition $(i,j)$ uniformly at random.

The random nearly-uniform (biased) transposition walk is the corresponding chain that at each time step applies a transposition $(i,j)$ with probability $p_{ij}$ for $p_{ij}$ comparable to the uniform rate up to uniformly bounded constants.

#### Problem 5.2.

[Igor Pak] Does the random nearly-uniform transposition walk on $S_n$ exhibit cutoff?

What about in the simpler case where $p_{ij}=p_{i}p_{j}$ for each $1\leq i,j\leq n$?
• ### Cutoff profile of random transpositions

#### Problem 5.3.

[Nathanaël Berestycki] Can we obtain the cutoff profile for the uniform random transposition walk on $S_n$?

Cite this as: AimPL: Markov chain mixing times, available at http://aimpl.org/markovmixing.