Cutoff phenomenon for the warp-transpose top with random shuffle

Subhajit Ghosh

Published 2021-01-03Version 1

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_n\wr 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 $g\in G_n,\;1\leq i< n$. We call this the warp-transpose top with random shuffle on $G_n\wr S_n$. We find the spectrum of the transition probability matrix for this shuffle. We prove that the mixing time for this shuffle is $O\left(n\log n+\frac{1}{2}n\log (|G_n|-1)\right)$. We show that this shuffle presents $\ell^2$-pre-cutoff at $n\log n+\frac{1}{2}n\log (|G_n|-1)$. We also show that this shuffle exhibits $\ell^2$-cutoff phenomenon with cutoff time $n\log n+\frac{1}{2}n\log (|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 $n\log n+\frac{1}{2}n\log (|G_n|-1)$ if $|G_n|=o(n^{\delta})$ for all $\delta>0$.