Loading Web-Font TeX/Math/Italic
| 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.