Cutoff phenomenon for the warp-transpose top with random shuffle


Abstract in English

Let ${G_n}_{1}^{infty}$ be a sequence of non-trivial finite groups, and $widehat{G}_n$ denote the set of all non-isomorphic irreducible representations of $G_n$. In this paper, we study the properties of a random walk on the complete monomial group $G_nwr S_n$ generated by the elements of the form $(text{e},dots,text{e},g;text{id})$ and $(text{e},dots,text{e},g^{-1},text{e},dots,text{e},g;(i,n))$ for $gin G_n,;1leq i< n$. We call this the warp-transpose top with random shuffle on $G_nwr S_n$. We find the spectrum of the transition probability matrix for this shuffle. We prove that the mixing time for this shuffle is $Oleft(nlog n+frac{1}{2}nlog (|G_n|-1)right)$. We show that this shuffle presents $ell^2$-pre-cutoff at $nlog n+frac{1}{2}nlog (|G_n|-1)$. We also show that this shuffle exhibits $ell^2$-cutoff phenomenon with cutoff time $nlog n+frac{1}{2}nlog (|G_n|-1)$ if $|widehat{G}_n|=o(|G_n|^{delta}n^{2+delta})$ for all $delta>0$. We prove that this shuffle has total variation cutoff at $nlog n+frac{1}{2}nlog (|G_n|-1)$ if $|G_n|=o(n^{delta})$ for all $delta>0$.

Download