| Register
\(\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


      Add remark

      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.

          Add remark

          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


              Add remark

              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.