%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{69}
\addbibresource{ref.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
%% note that the class file already loads {amsmath, amsthm, amssymb}
%--------THEOREM Envmnt------------
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{rem}[thm]{Remark}
\newtheorem{defn}[thm]{Definition}
\newtheorem{exmp}[thm]{Example}
%---------------Usepackage------------------
\usepackage{amsfonts,amstext,pgf,verbatim,textcomp,color,young,tikz,mathrsfs}
%\usepackage{lmodern}
%------------NEWCOMMAND---------
\newcommand{\Gr}{G_n}
\newcommand{\yirr}{\mathcal{Y}(\widehat{\Gr})}
\newcommand{\ynirr}{\mathcal{Y}_n(\widehat{\Gr})}
\newcommand{\irrG}{\widehat{\Gr}}
\newcommand{\tabG}{\tab_{\Gr}(n)}
%-----------MATH OPERATOR DECLARATION--------
\DeclareMathOperator{\TV}{TV}
\DeclareMathOperator{\1}{id}
\DeclareMathOperator{\trivial}{\mathbb{1}}
\DeclareMathOperator{\Tr}{trace}
\DeclareMathOperator{\dimension}{dim}
\DeclareMathOperator{\Gn}{\mathcal{G}_n}
\DeclareMathOperator{\G1}{e}
\DeclareMathOperator{\y}{\mathcal{Y}}
\DeclareMathOperator{\yn}{\mathcal{Y}_n}
\DeclareMathOperator{\yx}{\mathcal{Y}(X)}
\DeclareMathOperator{\ynx}{\mathcal{Y}_n(X)}
\DeclareMathOperator{\irrnG}{\widehat{\Gn}}
\DeclareMathOperator{\tab}{tab}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\std}{Std}
\DeclareMathOperator{\var}{Var_k(X)}
%% define your title in the usual way
\title{Cutoff for the warp-transpose top with random shuffle}
%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Subhajit Ghosh\thanks{\href{gsubhajit@iisc.ac.in}{gsubhajit@iisc.ac.in}. Supported by a UGC Centre for Advanced Study grant}\addressmark{1}}
%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Indian Institute of Science, Bangalore, India}
%% put the date of submission here
\received{\today}
%% leave this blank until submitting a revised version
%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We consider a random walk on the complete monomial group $\Gr\wr S_n$ generated by the elements of the forms $(\G1,\dots,\G1,g;\1)$ and $(\G1,\dots,\G1,g^{-1},\G1,\dots,\G1,g;(i,n))$ for $g\in \Gr,\;1\leq i< n$. We call this the warp-transpose top with random shuffle on $\Gr\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 of order $n\log n+\frac{1}{2}n\log (|\Gr|-1)$ and under some condition on $|\Gr|$, this shuffle exhibits the cutoff phenomenon.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{random walk, complete monomial group, mixing time, cutoff, Young--Jucys--Murphy elements}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%% note the \printbibliography command at the end of the file which goes with these biblatex commands
\begin{document}
\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}\label{intro}
Random walks on finite groups are well-studied topic in probability theory. Under certain natural conditions, a random walk converges to a unique stationary distribution. Random walks on finite groups can be used in various situations to approximate, understand and sample from their stationary distribution. For more details about random walks on finite groups, see \cite{S,D1,D2}. The topic of interest in this case is the mixing time i.e., the number of steps required to reach near the stationary distribution upto a given tolerance. To study the convergence of random walks, it is helpful to know the eigenvalues and eigenvectors of the transition matrix. In the eighties, the theory of random walks on finite groups obtained its own independence, its own problems and techniques. In an seminal work of Diaconis and Shahshahani \cite{DS}, they introduced the use of non-commutative Fourier analytic techniques. Before describing the random walk we are going to consider, let us first recall the definition of the complete monomial group. 

Let $\{\Gr\}_n$ be a sequence of finite groups (Assume $|\Gr|>1$ for all $n$) and $S_n$ be the symmetric group. The complete monomial group is the \emph{wreath product} of $\Gr$ with $S_n$, is a group denoted by $\Gn=\Gr\wr S_n$ and can be described as follows: The elements of $\Gn$ are $(n+1)$-tuples $(g_1,g_2,\dots,g_n;\pi)$ where $g_i\in \Gr$ and $\pi\in S_n$. The multiplication in $\Gn$ is given by
$(g_1,\dots,g_n;\pi)(h_1,\dots,h_n;\eta)=(g_1h_{\pi^{-1}(1)},\dots,g_nh_{\pi^{-1}(n)};\pi\eta).$
Therefore $(g_1,\dots,g_n;\pi)^{-1}=(g_{\pi(1)}^{-1},\dots,g_{\pi(n)}^{-1};\pi^{-1})$. Let $\G1$ be the identity of $\Gr$ and $\1$ be the identity of $S_n$. For an element $\pi\in S_n$, let $\pi:=(\G1,\dots,\G1;\pi)\in \Gn$ and for $g\in \Gr$, let $g^{(i)}:=(\G1,\dots,\G1,g,\G1,\dots,\G1;\1)\in \Gn$ ($g$ is in $i^{\text{th}}$ position). Let $(\G1,\dots,\G1,g^{-1},\G1,\dots,\G1,g;(i,n))$ be the element of $\Gn$ with $g^{-1}$ in $i^{\text{th}}$ position and $g$ in $n^{\text{th}}$ position, for $g\in \Gr,\;1\leq i < n$. One can check that $(g^{-1})^{(i)} g^{(n)}(i,n)$ is equal to $(\G1,\dots,\G1,g^{-1},\G1,\dots,\G1,g;(i,n))$ for $g\in \Gr,\;1\leq i < n$.

In this work we consider a random walk on the complete monomial group $\Gn$ driven by a probability measure $P$, defined as follows:
\begin{equation}\label{def of P}
P(x)=
\begin{cases}
\frac{1}{n|\Gr|}&\text{ if }x=(\G1,\dots,\G1,g;\1)\text{ for }g\in \Gr,\\
\frac{1}{n|\Gr|}&\text{ if }x=(\G1,\dots,\G1,g^{-1},\G1,\dots,\G1,g;(i,n))\text{ for }g\in \Gr,\;1\leq i < n,\\
0&\text{ otherwise}.
\end{cases}
\end{equation}
We call this the \emph{warp-transpose top with random shuffle} because at most times the $n^{\text{th}}$ component is multiplied by $g$ and the $i^{\text{th}}$ component is multiplied by $g^{-1}$ simultaneously, $g\in \Gr$, $1\leq i<n$. We now state the main theorem of this paper.
\begin{thm}\label{thm:cutoff_main}
	The mixing time for the warp-transpose top with random shuffle on $\Gn$ is of order $n\log n+\frac{1}{2}n\log (|\Gr|-1)$. Moreover if $|\Gr|=o(n^{\delta})$ for all $\delta>0$, then this shuffle satisfies the cutoff phenomenon.
\end{thm}

\subsection{Preliminaries}
Given a finite group $G$, the group algebra $\mathbb{C}[G]$ be the set of all formal linear combinations of the elements of $G$ with complex coefficients. $\mathbb{C}[G]$ can be thought of as a vector space over $\mathbb{C}$ with basis $G$. If we denote $V=\mathbb{C}[G]$ then the \emph{right regular representation} $R:G\longrightarrow GL(V)$ is defined by 
$g\mapsto\left(\sum_{h\in G}C_hh\mapsto\sum_{h\in G}C_hhg\right),\text{ where }C_h\in\mathbb{C}$ i.e., $R(g)$ is an invertible matrix over $\mathbb{C}$ of order $|G|\times|G|$. We will assume basic definitions and terminologies of finite group representations. We use some results from representation theory of finite groups without recalling the proof. For details about finite group representation see \cite{Amri,Sagan,Serre}. 

Let $\;p\text{ and }q$ be two probability measures on a finite group $G$. We define the \emph{convolution $p*q$} of $p$ and $q$ by $(p*q)(x):=\sum_{y\in G}p(xy^{-1})q(y)$. The \emph{Fourier transform} $\widehat{p}$ of $p$ at the right regular representation $R$ is defined by the matrix $\sum_{x\in G}p(x)R(x)$. The matrix $\widehat{p}(R)$ can be thought of as the action of the group algebra element $\sum_{g\in G}p(g)g$ on $\mathbb{C}[G]$ from the right. It can be easily seen that $\widehat{(p*q)}(R)=\widehat{p}(R)\widehat{q}(R)$.  

A \emph{random walk on a finite group $G$ driven by a probability measure $p$} is a Markov chain with state space $G$ and transition probabilities $M_p(x,y)=\;p(x^{-1}y)$, $x,y\in G$. It can be easily seen that the transition matrix $M_p$ is the transpose of $\widehat{p}(R)$ and the distribution after $k^{th}$ transition will be $p^{*k}$ (convolution of $p$ with itself $k$ times) i.e., the probability of getting into state $y$ starting at state $x$ after $k$ transitions is $p^{*k}(x^{-1}y)$. A random walk is said to be \emph{irreducible} if it is possible for the chain to reach any state starting from any state using only transitions of positive probabilities. One can easily check that the random walk on $G$ driven by $p$ is irreducible if and only if the support of $p$ generates $G$. A probability distribution $\Pi$ is said to be a \emph{stationary distribution} of a random walk with transition matrix $M$ if $\Pi M=\Pi$. Any irreducible random walk possesses a unique stationary distribution. The stationary distribution for an irreducible random walk on $G$ driven by $p$, is the uniform distribution $U_G$ on $G$. From now on, the uniform distribution on $G$ will be denoted by $U_G$. 
Given a random walk (discrete time, finite state space) the \emph{period} of a state $x$ is defined to be the greatest common divisor of the set of all times when it is possible for the chain to return to the starting state $x$. The period of all the states of an irreducible random walk are the same (see \cite[Lemma 1.6]{LPW}). An irreducible random walk is said to be \emph{aperiodic} if the common period for all its states is $1$.  

Let $\mu$ and $\nu$ be two probability measures on $\Omega$. The \emph{total variation distance} between $\mu$ and $\nu$ is defined by \[||\mu-\nu||_{\TV}:=\sup_{A\subset\Omega}|\mu(A)-\nu(A)|.\]
We note that $||\mu-\nu||_{\TV}=\frac{1}{2}\sum_{x\in\Omega}|\mu(x)-\nu(x)|$ (see \cite[Proposition 4.2]{LPW}). If the irreducible random walk on a finite group $G$ driven by a probability measure $p$ (defined on $G$) is aperiodic, then the distribution after $k^{\text{th}}$ transition converges to $U_{G}$ in total variation distance as $k\rightarrow\infty$. 
\begin{defn}\label{cutoff defn}
	Let $\{\mathscr{G}_n\}_{0}^{\infty}$ be a sequence of finite groups and $p_n$ be a probability measure on $\mathscr{G}_n$ for each $n$. Consider the sequence of irreducible and aperiodic random walks on $\mathscr{G}_n$ driven by $p_n$. We say that the \emph{total variation cutoff phenomenon} holds for the family $\{(\mathscr{G}_n,p_n)\}_0^{\infty}$ if there exists a sequence $\{\tau_n\}_0^{\infty}$ of positive real numbers tending to infinity such that the following hold:
	\begin{enumerate}
		\item For any $\epsilon\in (0,1)$ and $k_n=\lfloor(1+\epsilon)\tau_n\rfloor$, $\lim\limits_{n\rightarrow\infty}||p_n^{*k_{n}}-U_{\mathscr{G}_n}||_{\TV}=0$ and
		\item For any $\epsilon\in (0,1)$ and $k_n=\lfloor(1-\epsilon)\tau_n\rfloor$, $\lim\limits_{n\rightarrow\infty}||p_n^{*k_{n}}-U_{\mathscr{G}_n}||_{\TV}=1$.
	\end{enumerate}
	Here $\lfloor x\rfloor$ denotes the floor  of $x$ (the largest integer less than or equal to $x$). See \cite{DCutoff} for more details on cutoff phenomenon.
\end{defn}
\begin{prop}\label{irreducibility and aperiodicity}
	The warp-transpose top with random shuffle on $\Gn$ is irreducible and aperiodic.
\end{prop}
\begin{proof}
	 The support of $P$ is $\Gamma=\{(g^{-1})^{(i)}g^{(n)}(i,n),g^{(n)}\mid g\in \Gr,1\leq i<n\}$ and it can be easily seen that $\{g^{(k)},(i,n)\mid g\in \Gr,\;1\leq k\leq n,\;1\leq i<n\}$ is a generating set of $\Gn$. Thus \eqref{eq:Irredc+aperiodi} implies $\Gamma$ generates $\Gn$ and hence the warp-transpose top with random shuffle on $\Gn$ is irreducible.
	 \begin{equation}\label{eq:Irredc+aperiodi}
	 \begin{split}
	 & (g^{-1})^{(n)}\left((g^{-1})^{(i)}g^{(n)}(i,n)\right)g^{(n)}=(i,n)\text{ for each }1\leq i<n\text{ and }g\in \Gr,\\
	 & (k,n)g^{(n)}(k,n)=g^{(k)} \text{ for each }1\leq k\leq n\text{ and for all }g\in \Gr.
	 \end{split}
	 \end{equation}
	 Moreover given any $\pi\in \Gn$, the set of all times when it is possible for the chain to return to the starting state $\pi$ contains the integer $1$ (as support of $P$ contains the identity element of $\Gn$). Therefore the period of the state $\pi$ is $1$ and hence from irreducibility all the states of this chain have period $1$. Thus this chain is aperiodic.
\end{proof}
\cref{irreducibility and aperiodicity} says that the warp-transpose top with random shuffle on $\Gn$ converges to the uniform distribution $U_{\Gn}$ as the number of transitions goes to infinity.
In \cref{sec:representation} we will find the spectrum of $\widehat{P}(R)$. We will prove the theorem which gives an upper bound of $||P^{*k}-U_{\Gn}||_{\TV}$ in \cref{sec:upper bound}. In \cref{sec:lower bound}, lower bound of $||P^{*k}-U_{\Gn}||_{\TV}$ will be discussed and \cref{thm:cutoff_main} will be proved. Throughout this article $[n]$ denotes the set $\{1,\dots,n\}$ for any positive integer $n$.

%IF THERE IS SOME PAGE REMAINS THEN GIVE THE PHYSICAL DESCRIPTION OF THE MODEL.

%------------------EIGENVALUES OF $\widehat{P}(R)$-------------
\section{Spectrum of the transition matrix}\label{sec:representation}
In this section we find the eigenvalues of the transition matrix $\widehat{P}(R)$, the Fourier transform of $P$ at the right regular representation $R$ of $\Gn$. To find the eigenvalues of $\widehat{P}(R)$ we will use the representation theory of the wreath product $\Gn$ of a finite group $\Gr$ with the symmetric group $S_n$. First we briefly discuss the representation theory of $\Gn$, following the notation from \cite{MS}.

\begin{defn}\label{def: yx and ynx}
	Let $\y$ denote the set of all Young diagrams (there is a unique Young diagram with zero boxes) and $\yn$ denote the set of all Young diagrams with $n$-boxes. For a finite set $X$, we define $\yx=\{\mu:\mu\text{ is a map from }X\text{ to }\y\}$. For $\mu\in\yx$, define $||\mu||=\sum_{x\in X}|\mu(x)|$, where $|\mu(x)|$ is the number of boxes of the Young diagram $\mu(x)$ and define $\ynx=\{\mu\in\yx:||\mu||=n\}$.
\end{defn}
Let $\irrG$ denote the (finite) set of equivalence classes of finite dimensional complex irreducible representations of $\Gr$. Given $\sigma\in\irrG$, we denote by $W^{\sigma}$ the corresponding irreducible $\Gr$-module. Here by irreducible $\Gr$-module we mean the space for the corresponding irreducible representation of $\Gr$. Elements of $\yirr$ are called \emph{Young $\Gr$-diagrams} and elements of $\ynirr$ are called \emph{Young $\Gr$-diagrams with $n$ boxes}. Given $\mu\in\yirr$ and $\sigma\in\irrG$, we denote by $\mu\downarrow_{\sigma}$ the set of all Young $\Gr$-diagrams obtained from $\mu$ by removing one of the inner corners in the Young diagram $\mu(\sigma)$. Let $\mu\in\y$. A \emph{Young tableau} of shape $\mu$ is obtained by taking the Young diagram $\mu$ and filling its $|\mu|$ boxes (bijectively) with the numbers $1,2,\dots,|\mu|$. A Young tableau is said to be \emph{standard} if the numbers in the boxes strictly increase along each row and each column of the Young diagram of $\mu$. The set of all standard Young tableaux of shape $\mu$ is denoted by $\tab(\mu)$. 
%Let $\tab(\mu)$, where $\mu\in\yn$, denote the set of all standard Young tableaux of shape $\mu$ and let tab$(n)=\cup_{\mu\in\yn}\tab(\mu)$. 
Let $\mu\in\yirr$. A \emph{Young $\Gr$-tableau} of shape $\mu$ is obtained by taking the Young $\Gr$-diagram $\mu$ and filling its $||\mu||$ boxes (bijectively) with the numbers $1,2,\dots,||\mu||.$ A Young $\Gr$-tableau is said to be \emph{standard} if the numbers in the boxes strictly increase along each row and each column of all Young diagrams occurring in $\mu$. Let $\tab_{\Gr}(n,\mu)$, where $\mu\in\ynirr$, denote the set of all standard Young $\Gr$-tableaux of shape $\mu$ and let $\tabG=\cup_{\mu\in\ynirr}\tab_{\Gr}(n,\mu)$. Let $T\in\tabG$ and $i\in[n]$. If $i$ appear in the Young diagram $\mu(\sigma)$, where $\mu$ is the shape of $T$ and $\sigma\in\irrG$, we write $r_{T}(i)=\sigma$. The \emph{content} of a box in row $p$ and column $q$ of a Young diagram is the integer $q-p$. Let $b_T(i)$ be the box in $\mu(\sigma)$, with the number $i$ resides. Also $c(b_T(i))$ denotes the content of the box $b_T(i)$. The (generalized) \emph{Young--Jucys--Murphy} elements $X_1,X_2,\dots,X_n$ of $\mathbb{C}[\Gn]$ are given by $X_1= 0$ and 
\begin{equation*}
X_i=\sum\limits_{k=1}^{i-1}\sum\limits_{g\in \Gr}(g^{-1})^{(k)}g^{(i)}(k,i)=\sum\limits_{k=1}^{i-1}\sum\limits_{g\in \Gr}(g^{-1})^{(k)}(k,i)g^{(k)},\text{ for all }2\leq i\leq n.
\end{equation*}
We now define Gelfand--Tsetlin subspaces and the Gelfand--Tsetlin decomposition.
\begin{defn}\label{def: GZ-}
	Let $\lambda\in\irrnG$ and consider the irreducible $\Gn$-module (the space for the representation of $\Gn$) $V^{\lambda}$. Since the branching is simple \cite[Section 3]{MS}, the decomposition into irreducible $\mathcal{G}_{n-1}$-modules is given by 
	\[V^{\lambda}=\underset{\mu}{\oplus}V^{\mu},\]
	where the sum is over all $\mu\in \widehat{\mathcal{G}}_{n-1}$, with $\mu\nearrow\lambda$ (i.e there is an edge from $\mu$ to $\lambda$ in the branching multi-graph), is canonical. Iterating this decomposition of $V^{\lambda}$ into irreducible $\mathcal{G}_1$-submodules, i.e.,
	\begin{equation}\label{eq:GZ-}
	V^{\lambda}=\underset{T}{\oplus}V_{T},
	\end{equation}
	where the sum is over all possible chains $T=\lambda_1\nearrow\lambda_2\nearrow\dots\nearrow\lambda_n$ with $\lambda_i\in \widehat{\mathcal{G}}_i$ and $\lambda_n=\lambda$. We call \eqref{eq:GZ-} the \emph{Gelfand--Tsetlin} decomposition of $V^{\lambda}$ and each $V_T$ in \eqref{eq:GZ-} a \emph{Gelfand--Tsetlin} subspace of $V^{\lambda}$. We note that if $0\neq v_T\in V_T,\text{ then }\mathbb{C}[\mathcal{G}_i]v_T=V^{\lambda_i}$ from the definition of $V_T$. Unlike $\mathcal{G}_i=G_i\wr S_i$, here $\mathcal{G}_i$ denotes the subgroup of $\Gn$ given as follows 
	\[\mathcal{G}_i=\{(g_1,\dots,g_n,\pi)\in\Gn:\pi(j)=j\text{ for }i+1\leq j\leq n\},\;1\leq i\leq n.\]
	The Young--Jucys--Murphy elements act by scalars on the Gelfand--Tsetlin subspaces.
\end{defn}
From Lemma 6.2 and Theorem 6.4 of \cite{MS}, we may parametrize the irreducible representations of $\Gn$ by elements of $\mathcal{Y}_n(\irrG)$.
\begin{thm}[{\cite[Theorem 6.5]{MS}}]\label{thm:action of yjm els}
	Let $\mu\in\ynirr$. Then we may index the Gelfand--Tsetlin subspaces of $V^{\mu}$ by standard Young $\Gr$-tableaux  of shape $\mu$ and write the Gelfand--Tsetlin decomposition as 
	\[V^{\mu}=\underset{T\in\tab_{\Gr}(n,\mu)}{\oplus}V_T,\]
	where each $V_T$ is closed under the action of $\Gr^n$ and as a $\Gr^n$-module, is isomorphic to the irreducible $\Gr^n$-module 
	\[W^{r_T(1)}\otimes W^{r_T(2)}\otimes\dots\otimes W^{r_T(n)}.\]
	For $i=1,\dots,n;$ the eigenvalues of $X_i$ on $V_T$ are given by $\frac{|\Gr|}{\dimension(W^{r_T(i)})}c(b_T(i))$.
\end{thm}
\begin{thm}[{\cite[Theorem 6.7]{MS}}]\label{thm:dimen of irr G_n-modules}
Let $\mu\in\ynirr$. Write the elements of $\irrG$ as $\{\sigma_1,\dots,\sigma_t\}$ and set $\mu^{(i)}=\mu(\sigma_i),\;m_i=|\mu^{(i)}|,d_i=\dimension(W^{\sigma_i})$ for each $1\leq i\leq t$. Then 
\[\dimension(V^{\mu})=\binom{n}{m_1,\dots,m_t}f^{\mu^{(1)}}\cdots f^{\mu^{(t)}}d_1^{m_1}\cdots d_t^{m_t}.\]
Here $f^{\mu^{(i)}}$ denotes the number of standard Young tableau of shape $\mu^{(i)}$, for each $1\leq i\leq t$.
\end{thm}
Without loss of generality, from now on we will assume $\sigma_1=\trivial$ (the trivial representation of $\Gr$) and $\mu\left(\in\ynirr\right)$ as the tuple $(\mu^{(1)},\dots,\mu^{(t)})$. We note that for $T\in\tab_{\Gr}(n,\mu)$ the dimension of $V_T$ is $d_1^{m_1}\cdots d_t^{m_t}$, notations follow the same meaning as of \cref{thm:dimen of irr G_n-modules}. 
\begin{lem}\label{lem:only G-action}
	Let G be a finite group and $\sigma\in\widehat{G}$. If $W^{\sigma}\;($respectively $\chi^{\sigma})$ denotes the irreducible $G$-module $($respectively character$)$ 
	and $d_{\rho}$ is the dimension of $W^{\sigma}$, then the action of the group algebra element $\sum_{g\in G}g$ on $W^{\sigma}$ is given by the following scalar matrix
	\[\sum_{g\in G}g=\frac{|G|}{d_{\sigma}}\langle\chi^{\sigma},\chi^{\trivial}\rangle I_{d_{\sigma}}.\]
	Here $I_{d_{\sigma}}$ is the identity matrix of order $d_{\sigma}\times d_{\sigma}$.
	\end{lem}
\begin{proof}
	It is clear that $\sum_{g\in G}g$ is in the centre of $\mathbb{C}[G]$. Therefore by Schur's lemma (\cite[Proposition 4]{Serre}), we have $\sum_{g\in G}g=c I_{d_{\sigma}}$ for some $c\in\mathbb{C}$. The value of $c$ can be obtained by equating the traces of $\sum_{g\in G}g$ and $c I_{d_{\sigma}}$.
\end{proof}
\begin{thm}\label{thm: eigenvalues on irre}
	For each $\mu=(\mu^{(1)},\dots,\mu^{(t)})\in\ynirr$, let $\widehat{P}(R)\big|_{V^{\mu}}$ denotes the restriction of $\widehat{P}(R)$ to the irreducible $\Gn$-module $V^{\mu}$. Then the eigenvalues of $\widehat{P}(R)\big|_{V^{\mu}}$ are given by,
	\[\frac{1}{n\dimension(W^{r_T(n)})}\left(c(b_T(n))+\langle\chi^{r_T(n)},\chi^{\trivial}\rangle\right),\text{ with multiplicity }\dimension(V_T)=d_1^{m_1}\cdots d_t^{m_t}\]
	 for each $T\in\tab_{\Gr}(n,\mu)$. 
\end{thm}
\begin{proof}
	We first find the eigenvalues of $X_n+\sum_{g\in \Gr}(\G1,\dots,\G1,g;\1)$. Let $I_{\dimension(V_T)}$ denote the identity matrix of order $\dimension(V_T)\times\dimension(V_T)$. Then from \cref{thm:action of yjm els} we have
	\begin{equation}\label{eigenvalu_thm_eqn1}
	V^{\mu}=\underset{T\in\tab_{\Gr}(n,\mu)}{\oplus}V_T\quad\text{ and }\quad X_n\big|_{V_T}=\frac{|\Gr|}{\dimension(W^{r_T(n)})}c(b_T(n))I_{\dimension(V_T)}.
	\end{equation}
	Again from \cref{thm:action of yjm els} and \cref{lem:only G-action} we have
	\begin{equation}\label{eigenvalu_thm_eqn2}
	\sum_{g\in \Gr}(\G1,\dots,\G1,g;\1)\big|_{V_T}=\frac{|\Gr|}{\dimension(W^{r_T(n)})}\langle\chi^{r_T(n)},\chi^{\trivial}\rangle I_{\dimension(V_T)}.
	\end{equation} 
	\[\text{Also }\widehat{P}(R)=\frac{1}{n|\Gr|}\sum_{g\in \Gr}\left(R\left((\G1,\dots,\G1,g;\1)\right)+\sum_{i=1}^{n-1}R\left((\G1,\dots,\G1,g^{-1},\G1,\dots,\G1,g;(i,n))\right)\right).\]
	Therefore $n|\Gr|\widehat{P}(R)$ is nothing but the action of $X_n+\sum_{g\in \Gr}(\G1,\dots,\G1,g;\1)$ on $\mathbb{C}[\Gn]$ from right. Since $\dimension(V_T)=d_1^{m_1}\cdots d_t^{m_t}$, the theorem follows from \eqref{eigenvalu_thm_eqn1} and \eqref{eigenvalu_thm_eqn2}.
\end{proof}
\begin{rem}\label{rem:all eigenvalues}
	In the regular representation of a finite group, each irreducible representation occurs with multiplicity equal to its dimension \cite[Section 2.4]{Serre}. Therefore, \cref{thm:dimen of irr G_n-modules,thm: eigenvalues on irre} provide the eigenvalues of $\widehat{P}(R)$.
\end{rem}
%------------------LOWER BOUND FOR TOTAL VARIATION DISTANCE--------------
\section{Upper bound for total variation distance}\label{sec:upper bound}
In this section, we will prove the theorem giving an upper bound of the total variation distance $||P^{*k}-U_{\Gn}||_{\TV}$ using the upper bound lemma \cite[Lemma 4.2]{D1}. Before proving the main result of this section, first we prove some lemmas which will be useful. For any positive integer $\ell$, we write $\lambda\vdash\ell$ to denote $\lambda$ is a partition of $\ell$.
\begin{lem}\label{lem:UB_1}
	Let $\ell$ be a positive integer and $s$ be any non-negative real number. For $\lambda\vdash\ell$, if $\lambda_1$ denotes the largest part of $\lambda$, then
	\[\sum_{\lambda\vdash\ell}(f^{\lambda})^2\left(\frac{\lambda_1-s}{\ell}\right)^{2k}<e^{-\frac{2ks}{\ell}}e^{\ell^2e^{-\frac{2k}{\ell}}}.\]
\end{lem}
\begin{proof}
	For any partition $\zeta$ of $\ell-\lambda_1$ with largest part $\zeta_1\leq\lambda_1$, we have $f^{\lambda}\leq\binom{\ell}{\lambda_1}f^{\zeta}$. Therefore $\sum_{\lambda\vdash\ell}(f^{\lambda})^2\left(\frac{\lambda_1-s}{\ell}\right)^{2k}$ is less than or equal to 
	\begin{align}\label{eq:UB_1.1}
	\sum_{\lambda_1=1}^{\ell}\sum_{\substack{\zeta\vdash(\ell-\lambda_1)\\\zeta_1\leq\lambda_1}}\binom{\ell}{\lambda_1}^2(f^{\zeta})^2\left(\frac{\lambda_1-s}{\ell}\right)^{2k}&\leq\sum_{\lambda_1=1}^{\ell}\binom{\ell}{\lambda_1}^2\left(\frac{\lambda_1-s}{\ell}\right)^{2k}\sum_{\zeta\vdash(\ell-\lambda_1)}(f^{\zeta})^2\nonumber\\
	&=\sum_{u=0}^{\ell-1}\binom{\ell}{u}^2\left(1-\frac{u+s}{\ell}\right)^{2k}u!.
	\end{align}
	Equality in \eqref{eq:UB_1.1} is obtained by writing $u=\ell-\lambda_1$. Using $1-x\leq e^{-x}$ for all $x\geq 0$ and $\binom{\ell}{u}\leq\frac{\ell^u}{u!}$, the expression in the right hand side of \eqref{eq:UB_1.1} is less than or equal to
	\[\sum_{u=0}^{\ell-1}\frac{\ell^{2u}}{u!}e^{-\frac{2k}{\ell}(u+s)}<e^{-\frac{2ks}{\ell}}\sum_{u=0}^{\infty}\frac{1}{u!}\left(\ell^2e^{-\frac{2k}{\ell}}\right)^u=e^{-\frac{2ks}{\ell}}e^{\ell^2e^{-\frac{2k}{\ell}}}.\]
\end{proof}
\begin{cor}\label{rem:UB_1}
	Following the notations of \cref{lem:UB_1}, we have
	\[\sum_{\substack{\lambda\vdash\ell\\\lambda\neq (\ell)}}(f^{\lambda})^2\left(\frac{\lambda_1-s}{\ell}\right)^{2k}<e^{-\frac{2ks}{\ell}}e^{\ell^2e^{-\frac{2k}{\ell}}}-\left(\frac{\ell-s}{\ell}\right)^{2k}.\]
\end{cor}
\begin{lem}\label{lem:UB_2}
	Following the notations from \cref{thm:action of yjm els,thm:dimen of irr G_n-modules} we have
	\begin{align*}
	&\sum_{T\in\tab_{\Gr}(n,\mu)}\left(\frac{c(b_T(n))+\langle\chi^{r_T(n)},\chi^{\trivial}\rangle}{n\dimension(W^{r_T(n)})}\right)^{2k}\\
	<&\;\binom{n}{m_1,\dots, m_t}f^{\mu^{(1)}}\cdots f^{\mu^{(t)}}\sum_{j=1}^{t}\left(\frac{\mu^{(j)}_1-1+\langle\chi^{\sigma_j},\chi^{\trivial}\rangle}{nd_j}\right)^{2k}.
	\end{align*}
	Here $\mu^{(i)}_1$ denotes the largest part of the partition $\mu^{(i)}$ for each $1\leq i\leq t$.
\end{lem}
\begin{proof}
	The set $\tab_{\Gr}(n,\mu)$ is a disjoint union of the sets $\mathcal{T}_1,\dots,\mathcal{T}_t$, where \[\mathcal{T}_i=\{(T_1,\dots,T_t)\in\tab_{\Gr}(n,\mu)\mid b_T(n)\text{ is in }T_i\}\]
	for each $1\leq i\leq t.$ Therefore
	\begin{align}\label{eq:UB_2.1} &\displaystyle\sum_{T\in\tab_{\Gr}(n,\mu)}\left(\frac{c(b_T(n))+\langle\chi^{r_T(n)},\chi^{\trivial}\rangle}{n\dimension(W^{r_T(n)})}\right)^{2k}=\displaystyle\sum_{i=1}^{t}\displaystyle\sum_{T\in\mathcal{T}_i}\left(\frac{c(b_T(n))+\langle\chi^{\sigma_i},\chi^{\trivial}\rangle}{nd_i}\right)^{2k}\nonumber\\
	=&\sum_{i=1}^{t}\left(\frac{1}{d_i}\right)^{2k}\binom{n-1}{m_1,\dots,m_i-1,\dots,m_t}\frac{f^{\mu^{(1)}}\cdots f^{\mu^{(t)}}}{f^{\mu^{(i)}}}\sum_{T_i\in\tab(\mu^{(i)})}\left(\frac{c(b_T(m_i))+\langle\chi^{\sigma_i},\chi^{\trivial}\rangle}{n}\right)^{2k}\nonumber\\
	<&\sum_{i=1}^{t}\left(\frac{1}{d_i}\right)^{2k}\binom{n}{m_1,\dots,m_t}\frac{f^{\mu^{(1)}}\cdots f^{\mu^{(t)}}}{f^{\mu^{(i)}}}\sum_{T_i\in\tab(\mu^{(i)})}\left(\frac{\mu^{(i)}_1-1+\langle\chi^{\sigma_i},\chi^{\trivial}\rangle}{n}\right)^{2k}.
	\end{align}
	The result follows from $\displaystyle\sum_{T_i\in\tab(\mu^{(i)})}\left(\frac{\mu^{(i)}_1-1+\langle\chi^{\sigma_i},\chi^{\trivial}\rangle}{n}\right)^{2k}=f^{\mu^{(i)}}\left(\frac{\mu^{(i)}_1-1+\langle\chi^{\sigma_i},\chi^{\trivial}\rangle}{n}\right)^{2k}$ and \eqref{eq:UB_2.1}.
\end{proof}
\begin{prop}\label{prop:key_ineq}
For the warp-transpose top with random shuffle on $\Gn$ driven by $P$, we have 
\begin{align*}
4\;||P^{*k}-U_{\Gn}||^2_{\TV}\;<\;&\;\left(e^{n^2e^{-\frac{2k}{n}}}-1\right)+e\left(e^{n^2\left(|\Gr|-1\right)e^{-\frac{2k}{n}}}-1\right)\\
+&(t-1)\left(e^{-\frac{2k}{n}}e^{n^2e^{-\frac{2k}{n}}}+\frac{e}{n^2}\;\left(e^{n^2\left(|\Gr|-1\right)e^{-\frac{2k}{n}}}-1\right)\right),
\end{align*}
 for all $k\geq n\log n$.
\end{prop}
\begin{proof}
	Using the upper bound lemma \cite[Lemma 4.2]{D1}, we have
\begin{equation}\label{eq:key_ineq_1}
	4\;||P^{*k}-U_{\Gn}||^2_{\TV}\leq\sum_{\mu\in\ynirr : \;\mu(\trivial)\neq(n)}\dimension(V^{\mu})\Tr\left(\left(\widehat{P}(R)\big|_{V^{\mu}}\right)^{2k}\right).
\end{equation}
	Here we recall that $\irrG=\{\sigma_1,\dots,\sigma_t\}\text{ and }\sigma_1=\trivial$, the trivial representation of $\Gr$. Given $\mu\in\ynirr$, throughout this proof we write $\mu=(\mu^{(1)},\dots,\mu^{(t)})$, where $\mu^{(i)}\vdash m_i$ and $\sum_{i=1}^{t}m_i=n$. First we partition the set $\ynirr$ into two disjoint subsets $\mathcal{A}_1, \mathcal{A}_2$ as follows:
	\begin{align*}
	\mathcal{A}_1=\underset{1\leq i\leq t}{\cup}\mathcal{B}_i,\text{ where }
	\mathcal{B}_i&=\{\mu\in\ynirr\mid m_i=n,\; m_k=0\text{ for all }k\in[t]\setminus\{i\}\}\\
	\mathcal{A}_2&=\{\mu\in\ynirr\mid \sum_{k=1}^{t}m_k=n,\;0\leq m_k\leq n-1\}.
	\end{align*}
	It can be easily seen that $\mathcal{B}_i$'s are disjoint. Therefore by using \cref{thm: eigenvalues on irre} and \cref{rem:all eigenvalues}, the inequality \eqref{eq:key_ineq_1} become 
	 \begin{align}\label{eq:key_ineq_2}
	 	4\;||P^{*k}-&U_{\Gn}||^2_{\TV}\leq\sum_{\substack{\mu\in \mathcal{B}_1\\\mu(\trivial)\neq(n)}}\dimension(V^{\mu})\sum_{T\in\tab_{\Gr}(n,\mu)}\left(\frac{c(b_T(n))+1}{nd_1}\right)^{2k}d_1^{n}\nonumber\\
	 &+\sum_{i=2}^{t}\sum_{\mu\in \mathcal{B}_i}\dimension(V^{\mu})\sum_{T\in\tab_{\Gr}(n,\mu)}\left(\frac{c(b_T(n))}{nd_i}\right)^{2k}d_i^{n}\\
	 &+\sum_{\mu\in \mathcal{A}_2}\dimension(V^{\mu})\sum_{T\in\tab_{\Gr}(n,\mu)}\left(\frac{c(b_T(n))+\langle\chi^{r_T(n)},\chi^{\trivial}\rangle}{n\dimension(W^{r_T(n)})}\right)^{2k}d_1^{m_1}\cdots d_t^{m_t}.\nonumber
	 \end{align}
Given a partition $\xi$ of any positive integer, now on the largest part of $\xi$ will be denoted by $\xi_1$. The first two terms in the right hand side of inequality \eqref{eq:key_ineq_2} is equal to
\begin{align}\label{eq:key_ineq_2.1}
&\sum_{\substack{\lambda\vdash n\\\lambda_1\neq n}}f^{\lambda}d_1^n\sum_{T\in\tab(\lambda)}\left(\frac{c(b_T(n))+1}{nd_1}\right)^{2k}d_1^{n}+\sum_{i=2}^{t}\sum_{\lambda\vdash n}f^{\lambda}d_i^n\sum_{T\in\tab(\lambda)}\left(\frac{c(b_T(n))}{nd_i}\right)^{2k}d_i^{n}\nonumber\\
\leq &\; \frac{1}{d_1^{2k-2n}}\sum_{\substack{\lambda\vdash n\\\lambda_1\neq n}}f^{\lambda}\sum_{T\in\tab(\lambda)}\left(\frac{\lambda_1}{n}\right)^{2k}+\sum_{i=2}^{t}\frac{1}{d_i^{2k-2n}}\sum_{\lambda\vdash n}f^{\lambda}\sum_{T\in\tab(\lambda)}\left(\frac{\lambda_1-1}{n}\right)^{2k}\nonumber\\
\leq &\;\sum_{\substack{\lambda\vdash n\\\lambda_1\neq n}}(f^{\lambda})^2\left(\frac{\lambda_1}{n}\right)^{2k}+\sum_{i=2}^{t}\sum_{\lambda\vdash n}(f^{\lambda})^2\left(\frac{\lambda_1-1}{n}\right)^{2k}\nonumber\\
< & \; \left(e^{n^2e^{-\frac{2k}{n}}}-1\right)+(t-1)e^{-\frac{2k}{n}}e^{n^2e^{-\frac{2k}{n}}}.
\end{align}
The inequality in \eqref{eq:key_ineq_2.1} follows from \cref{lem:UB_1} and \cref{rem:UB_1}. 
Using \cref{lem:UB_2}, the third term in the right hand side of \eqref{eq:key_ineq_2} is less than
\begin{align}\label{eq:key_ineq_2.2}
\sum_{\mu\in \mathcal{A}_2}\binom{n}{m_1,\dots, m_t}^2(f^{\mu^{(1)}})^2\cdots (f^{\mu^{(t)}})^2d_1^{2m_1}\dots d_t^{2m_t}\sum_{j=1}^{t}\left(\frac{\mu^{(j)}_1-1+\langle\chi^{\sigma_i},\chi^{\trivial}\rangle}{nd_j}\right)^{2k}.
\end{align}
We now deal with \eqref{eq:key_ineq_2.2} by considering two separate cases namely $j=1$ and $1<j\leq t$. The partial sum corresponding to $j=1$ in \eqref{eq:key_ineq_2.2} equal to
\begin{align}\label{eq:key_ineq_j_1.1}
&\sum_{m_1=0}^{n-1}\sum_{\substack{(m_2,\dots,m_t)\\\sum m_k=n-m_1\\\\0\leq m_k\leq n-1}}\sum_{\substack{\mu^{(i)}\vdash m_i\\1\leq i\leq t}}\binom{n}{m_1}^2\binom{n-m_1}{m_2,\dots,m_t}^2(f^{\mu^{(1)}})^2\cdots (f^{\mu^{(t)}})^2d_1^{2m_1}\dots d_t^{2m_t}\left(\frac{\mu^{(1)}_1}{nd_1}\right)^{2k}\nonumber\\
<&\sum_{m_1=0}^{n-1}\sum_{\substack{(m_2,\dots,m_t)\\\sum m_k=n-m_1\\m_k\geq 0}}\sum_{\substack{\mu^{(i)}\vdash m_i\\1\leq i\leq t}}\binom{n}{m_1}^2\binom{n-m_1}{m_2,\dots,m_t}^2(f^{\mu^{(1)}})^2\cdots (f^{\mu^{(t)}})^2d_1^{2m_1}\dots d_t^{2m_t}\left(\frac{\mu^{(1)}_1}{nd_1}\right)^{2k}\nonumber\\
=&\sum_{m_1=0}^{n-1}(d_2^2+\cdots+d_t^2)^{n-m_1}\binom{n}{m_1}^2(n-m_1)!\left(\frac{1}{d_1}\right)^{2k-2m_1}\left(\frac{m_1}{n}\right)^{2k}\sum_{\mu^{(1)}\vdash m_1}(f^{\mu^{(1)}})^2\left(\frac{\mu^{(1)}_1}{m_1}\right)^{2k}\nonumber\\
<&\sum_{m_1=0}^{n-1}(d_2^2+\cdots+d_t^2)^{n-m_1}\binom{n}{m_1}^2(n-m_1)!\left(\frac{1}{d_1}\right)^{2k-2m_1}\left(\frac{m_1}{n}\right)^{2k}e^{m_1^2e^{-\frac{2k}{m_1}}}.
\end{align}
The inequality in \eqref{eq:key_ineq_j_1.1} follows from \cref{lem:UB_1}. As $k\geq n\log n$, we have $k\geq m_1\log m_1$ and $k\geq n$. Thus using $1-x\leq e^{-x}$ for all $x\geq 0$ and writing $n-m_1$ by $u$, the expression in \eqref{eq:key_ineq_j_1.1} is less than or equal to 
\begin{align}\label{eq:key_ineq_j_1.2}
&e\;\sum_{u=1}^{n}\left(\frac{d_2^2+\cdots+d_t^2}{d_1^2}\right)^u\left(\frac{1}{d_1}\right)^{2k-2n}\binom{n}{u}^2u!\left(1-\frac{u}{n}\right)^{2k}\nonumber\\
\leq\;&e\;\sum_{u=1}^{n}\frac{1}{u!}\left(n^2\left(\frac{|\Gr|}{d_1^2}-1\right)e^{-\frac{2k}{n}}\right)^u\;<e\left(e^{\left(n^2\left(\frac{|\Gr|}{d_1^2}-1\right)e^{-\frac{2k}{n}}\right)}-1\right).
\end{align}
By carrying out similar process as of $j=1$, the partial sum corresponding to $1<j\leq t$ in \eqref{eq:key_ineq_2.2} turns out to be
\begin{align}\label{eq:key_ineq_j>1}
\frac{e}{n^2}\left(e^{\left(n^2\left(\frac{|\Gr|}{d_j^2}-1\right)e^{-\frac{2k}{n}}\right)}-1\right).
\end{align}
Using $\frac{1}{d_j}\leq 1$ for all $1\leq j\leq t$, the proposition follows from \eqref{eq:key_ineq_2}, \eqref{eq:key_ineq_2.1}, \eqref{eq:key_ineq_j_1.2} and \eqref{eq:key_ineq_j>1}.
\end{proof}
\begin{thm}\label{thm:G_n Upper Bound}
	Recall that, $|\widehat{\Gr}|$ denotes the number of irreducible representations of $\Gr$. For the random walk on $\Gn$ driven by $P$, we have the following:
	\begin{enumerate}
		\item Let $|\widehat{\Gr}|>e+1$ and $c>\frac{1}{2}$. Then for $k\geq n\log n+\frac{1}{2}n\log (|\Gr|-1)+cn\log(|\widehat{\Gr}|-1)$, we have
		\[||P^{*k}-U_{\Gn}||_{\TV}<\sqrt{\frac{e+1}{2}}\;e^{-c}+o(1).\]
		For $|\widehat{\Gr}|=2,3$ take $k\geq n\log n+\frac{1}{2}n\log (|\Gr|-1)+cn$.
		\item  For any $\epsilon\in (0,1)$, if $|\widehat{\Gr}|=O(n^2)$ then $k_n=\lfloor(1+\epsilon)\left(n\log n+\frac{1}{2}n\log (|\Gr|-1)\right)\rfloor$ implies
		\[\lim\limits_{n\rightarrow\infty}||P^{*k_n}-U_{\Gn}||_{\TV}=0.\]
	\end{enumerate}
\end{thm}
\begin{proof}
	This follows from \cref{prop:key_ineq} and straightforward calculations.
\end{proof}

%------------------LOWER BOUND FOR TOTAL VARIATION DISTANCE--------------
\section{Lower bound for total variation distance}\label{sec:lower bound}
In this section, our focus will be on a lower bound of the total variation distance $||P^{*k}-U_{\Gn}||_{\TV}$. We will give the outline without details. The details will appear in a later publication \cite{Fullversion}. Also we prove \cref{thm:cutoff_main} in this section. To start, we define an auxiliary representation $\rho$ of $\Gn$ and a random variable $X$ on $\Gn$. 

Let $V=\mathbb{C}[\Gr\times [n]]$ be the complex vector space of all formal linear combinations of elements of $\Gr\times [n]$ and $GL(V)$ be the set of all invertible linear maps from $V$ to itself. We now define the representation $\rho: \Gn\longrightarrow GL(V)$ on the basis elements of $V$ by 
\[\rho(g_1,\dots,g_n;\pi)\left((h,i)\right)=\left(g_{\pi(i)}h,\pi(i)\right).\]
The random variable $X$ counts the number of fixed points of the action of $\rho$, i.e. $X$ is the character of $\rho$. Let $E_k(X)$ be the expectation and $V_k(X)$ the variance of $X$ with respect to the probability measure $P^{*k}$ on $\Gn$. $E_{U}(X)$ denotes the expectation of $X$ with respect to the uniform distribution on $\Gn$. It can be seen that $E_U(X)=1$.
\begin{thm}\label{thm: G_n Lower Bound}
If $|\Gr|=o(n^{\delta})$ for every $\delta>0$, then $\lim\limits_{n\rightarrow\infty}||P^{*k_n}-U_{\mathcal{G}_n}||_{\TV}=1$ for any $\epsilon\in (0,1)$ and $k_n=\lfloor(1-\epsilon)\left(n\log n+\frac{1}{2}n\log(|\Gr|-1)\right)\rfloor$.
\end{thm}
\begin{proof}
	Using Chebychev's and Markov's inequality first we obtain,
	\begin{equation}\label{eq:LB main ineq}
	||P^{*k}-U_{\Gn}||_{\TV}\geq 1-\frac{4V_k(X)}{(E_k(X))^2}-\frac{2}{E_k(X)}.
	\end{equation}
The theorem now follows by putting the values of $E_k(X)$ and $V_k(X)$ in \eqref{eq:LB main ineq}.
\end{proof}
\begin{proof}[Proof of \cref{thm:cutoff_main}]
	The first part of \cref{thm:G_n Upper Bound} implies that the mixing time for this shuffle is of order $n\log n+\frac{1}{2}n\log(|\Gr|-1)$ and the second part of \cref{thm:G_n Upper Bound} and \cref{thm: G_n Lower Bound} prove that the warp-transpose top with random shuffle on $\Gn$ satisfies the cutoff phenomenon.
\end{proof}
%-------------------Acknowledgements------------
\acknowledgements{ I would like to thank my advisor Arvind Ayyer for all the insightful discussions during the preparation of this paper. I would also like to thank the anonymous reviewer of FPSAC 2019 for the suggestion to extend the work from the $S_2\wr S_n$ to $G\wr S_n$. I would like to acknowledge support in part by a UGC Centre for Advanced Study grant.}
%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography
\end{document}
