Total variation cutoff for the flip-transpose top with random shuffle
Subhajit Ghosh



[Subhajit Ghosh]Department of Mathematics, Indian Institute of Science, Bangalore 560 012
gsubhajit@iisc.ac.in

[2010]60J10, 60B15, 60C05.


We consider a random walk on the hyperoctahedral group B_n generated by the signed permutations of the forms (i,n) and (-i,n) for 1≤ i≤ n. We call this the flip-transpose top with random shuffle on B_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 nlog n. We also show that this shuffle exhibits the cutoff phenomenon. In the appendix, we show that a similar random walk on the demihyperoctahedral group D_n also has a cutoff at (n-1/2)log n.

Total variation cutoff for the flip-transpose top with random shuffle
    Subhajit Ghosh
    December 30, 2023
=====================================================================





§ INTRODUCTION

Card shuffling problems are mathematically analysed by considering them as random walks on symmetric groups <cit.>. In this paper, our main aim is to study the properties of a random walk on Coxeter groups of type B <cit.>. This work is a generalisation of the transpose top with random shuffle <cit.> to the signed permutations. A signed permutation <cit.> is a bijection π from {±1,…,± n} to itself satisfying π(-i)=-π(i) for all 1≤ i≤ n. A signed permutation is completely determined by its image on the set [n]:={1,…,n}. Given a signed permutation π, we write it in window notation by [π_1,…,π_n], where π_i is the image of i under π. The set of all signed permutations forms a group under composition and is known as the hyperoctahedral group and is denoted by B_n. The subset of B_n consisting of those signed permutations having even number of negative entries in their window notation form a subgroup of B_n, called the demihyperoctahedral group and is denoted by D_n.

Suppose there are n cards labelled from 1 to n and each card has two orientations namely `face up' and `face down'. Given an arrangement of these n cards in a row, we associate a signed permutation [π_1,π_2,…,π_n] to it in the following way: π_i is the label of the ith card (counting started from left) with sign  

    positive,   if the orientation of the card is `face up' and
    negative,   if the orientation of the card is `face down'.

Thus every arrangement of the n cards in a row represents a signed permutation in its window notation. We consider the following shuffle on the set of all arrangements of these n cards in a row: Given an arrangement, either interchange the last card with a random card, or interchange the last card with a random card and flip both of them, with equal probability. We call this shuffle the flip-transpose top with random shuffle. Formally, this shuffle is the random walk on B_n driven by the probability measure P on B_n, given by

    P(π)=
    1/2n,   if π=, the identity element of B_n,
    1/2n,   if π=(i,n) for 1≤ i≤ n-1,
    1/2n,   if π=(-i,n) for 1≤ i≤ n,
     0,   otherwise.

We study the flip-transpose top with random shuffle on B_n using the representation theory of B_n. However, the moves are not the same for elements of the same conjugacy class (i.e., the generating measure does not take the same value at the elements of the same conjugacy class, we abbreviate such shuffle/walk as the non-conjugacy class shuffle/walk). In general, it is not easy to study non-conjugacy class walks on finite groups using the representation theory of the underlying groups. Some examples of such non-conjugacy class walks are the random-to-top shuffle <cit.> (this is an example of the Tsetlin library problem <cit.>), the random-to-random shuffle <cit.>, the one-sided transposition shuffle on the symmetric group <cit.>, and its generalisation to the hyperoctahedral group <cit.>. In this paper, we will show that the flip-transpose top with random shuffle on B_n satisfies the cutoff phenomenon and determine the mixing time for this random walk. Particularly if ||P^*k-U_B_n||_TV denotes the total variation distance between the distribution after k transitions and the stationary distribution, then the main results of this paper are the following:

	For the flip-transpose top with random shuffle on B_n, we have the following:
	
		
  * ||P^*k-U_B_n||_TV<√(2(e+1)) e^-c+o(1), for k≥ nlog n+cn and c>0.
		
  * lim_n→∞||P^*k_n-U_B_n||_TV=0, for any ϵ∈ (0,1) and k_n=⌊(1+ϵ)nlog n⌋.
	


	For the flip-transpose top with random shuffle on B_n, we have the following:
	
		
  * For large n, ||P^*k-U_B_n||_TV≥1-2(3+3e^-c+o(1)(e^-2c+e^-c+1))/(1+(1+o(1))e^-c)^2, when k=nlog n+cn and c≪0.
		
  * lim_n→∞||P^*k_n-U_B_n||_TV=1, for any ϵ∈ (0,1) and k_n=⌊(1-ϵ)nlog n⌋.
	

We will first recall some concepts and terminologies which we will use in this paper frequently.


 §.§ Representation theoretic background

Let V be a finite-dimensional complex vector space and GL(V) be the group of all invertible linear operators from V to itself under the composition of linear mappings. Elements of GL(V) can be thought of as invertible matrices over ℂ. Let G be a finite group, a mapping ρ:G→ GL(V) is said to be a linear representation of G if ρ(g_1g_2)=ρ(g_1)ρ(g_2) for all g_1, g_2 in G. The dimension of the vector space V is said to be the dimension of the representation ρ and is denoted by d_ρ. V is called the G-module corresponding to the representation ρ in this case. If ℂ[G]={∑_ic_ig_i| c_i∈ℂ,  g_i∈ G}, then we define the right regular representation R:G⟶ GL(ℂ[G]) of G by 

    R(g)(∑_h∈ GC_hh)=∑_h∈ GC_hhg, where C_h∈ℂ.

Let H be a subgroup of G. The restriction of the representation ρ to H is denoted by ρ↓^G_H and is defined by ρ↓^G_H(h):=ρ(h) for all h∈ H. The trace of the matrix ρ(g) is said to be the character value of ρ at g and is denoted by χ^ρ(g). A vector subspace W of V is said to be stable ( or `invariant') under ρ if ρ(g)(W)⊂ W for all g in G. The representation ρ is irreducible if V is non-trivial and V has no non-trivial proper stable subspace. Two representations (ρ_1,V_1) and (ρ_2,V_2) of G are said to be isomorphic if there exists an invertible linear map T:V_1→ V_2 such that the following diagram commutes for all g∈ G:

    V_1rρ_1(g)[swap]dT    V_1dT
    
    V_2rρ_2(g)    V_2

If V_1⊗ V_2 denotes the tensor product of the vector spaces V_1 and V_2, then the tensor product of two representations ρ_1: G→ GL(V_1) and ρ_2: G→ GL(V_2) is a representation denoted by (ρ_1⊗ρ_2,V_1⊗ V_2) and defined by,

    (ρ_1⊗ρ_2)(g)(v_1⊗ v_2)=ρ_1(g)(v_1)⊗ρ_2(g)(v_2)  for v_1∈ V_1,v_2∈ V_2 and g∈ G.

We will state some results from the representation theory of finite groups without proof. For more details, see <cit.>.


 §.§ Random walks on finite groups
 We first recall some terminology. Let p and q be two probability measures on a finite group G. The Fourier transform p of p at the representation ρ is defined by the matrix ∑_x∈ Gp(x)ρ(x). We define the convolution p*q of p and q by 
    (p*q)(x):=∑_{u,v∈ G| uv=x}p(u)q(v).
 
It can be easily seen that (p*q)(ρ)=p(ρ)q(ρ). For the right regular representation R, the matrix p(R) can be thought of as the action of the group algebra element ∑_g∈ Gp(g)g on ℂ[G] by multiplication on the right. 

A random walk on a finite group G driven by a probability measure p is a discrete time Markov chain with state space G and transition probabilities M_p(x,y)= p(x^-1y), x,y∈ G. The transition matrix M_p is the transpose of p(R). If p^*k denotes the k-fold convolution of p with itself, then the probability of reaching state y starting from state x using k transitions is p^*k(x^-1y). The random walk is said to be irreducible if given any two states u and v there exists t (depending on u and v) such that p^*t(u^-1v)>0. We now state the lemma regarding the irreducibility of the random walk on G driven by p.

Let G be a finite group and p be a probability measure on G. The random walk on G driven by p is irreducible if and only if the support of p generates G.

 A probability vector (a row vector with non-negative components which sum to one) Π is said to be a stationary distribution of the random walk if Π is a left eigenvector of the transition matrix with eigenvalue 1. There exists a unique stationary distribution for each irreducible random walk. If the random walk on G driven by p is irreducible, then the stationary distribution for this random walk is the uniform distribution on G <cit.>. From now on, we denote the uniform distribution on G by U_G. Let us consider a random walk and fix one state x∈ G. The greatest common divisor of the set of all times when it is possible for the walk to return to the starting state x is said to be the period of the state x. All the states of an irreducible random walk have the same period (see <cit.>). An irreducible random walk is said to be aperiodic if the common period for all its states is 1.  

Let μ and ν be two probability distributions on Ω. The total variation distance between μ and ν is defined by 
    ||μ-ν||_TV:=sup_A⊂Ω|μ(A)-ν(A)|.

The total variation distance between two discrete distributions μ and ν is half the ℓ_1 distance between them (see <cit.>). If the random walk on a finite group G driven by a probability measure on G is irreducible and aperiodic, then the distribution after the kth transition converges to the uniform measure on G as k→∞. We now define the total variation cutoff phenomenon.

 Let {𝒢_n}_0^∞ be a sequence of finite groups and p_n be probability measures on 𝒢_n, n≥ 0. For each n≥ 0, consider the irreducible and aperiodic random walks on 𝒢_n driven by p_n. We say that the total variation cutoff phenomenon holds for the family {(𝒢_n,p_n)}_0^∞ if there exists a sequence {τ_n}_0^∞ of positive real numbers such that the following hold:


  * lim_n→∞τ_n=∞,

  * For any ϵ∈ (0,1) and k_n=⌊(1+ϵ)τ_n⌋, lim_n→∞||p_n^*k_n-U_𝒢_n||_TV=0 and

  * For any ϵ∈ (0,1) and k_n=⌊(1-ϵ)τ_n⌋, lim_n→∞||p_n^*k_n-U_𝒢_n||_TV=1.

Here ⌊ x⌋ denotes the floor  of x (the largest integer less than or equal to x).

Informally, we will say that {(𝒢_n,p_n)}_0^∞ has a total variation cutoff at time τ_n. Roughly the cutoff phenomenon depends on the multiplicity of the second largest eigenvalue of the transition matrix <cit.>.

The flip-transpose top with random shuffle on B_n is irreducible and aperiodic.


We know that the set {(-1,1), (1,2), (2,3), …, (n-1,n)} generates B_n. Let i be any integer from [n-1]. Then (i,i+1)=(i+1,n)(i,n)(i+1,n) and (-1,1)=(1,n)(-n,n)(1,n). Therefore the support of the measure P generates B_n, and hence the chain is irreducible by Lemma <ref>. Given any π∈ B_n, the set of all times when it is possible for the chain to return to the starting state π contains the integer 1 (∵ the identity element of B_n is in support of P). Therefore the period of the state π is 1 and hence from irreducibility all the states of this chain have period 1. Thus this chain is aperiodic.

Proposition <ref> says that the flip-transpose top with random shuffle on B_n has unique stationary distribution U_B_n and the distribution after the kth transition will converge to its stationary distribution as k→∞. 

The plan of the rest of the paper is as follows: In Section <ref>, we will find the spectrum of the transition matrix P(R). We will find an upper bound of ||P^*k-U_B_n||_TV for k≥ nlog n+cn, c>0 in Section <ref>. Finally, in Section <ref>, we will find a lower bound of ||P^*k-U_B_n||_TV for k=nlog n+cn, c≪ 0 (large negative number) and show that the total variation cutoff for the shuffle on B_n occurs at nlog n.

In Appendix A, we give an outline of the irreducible representations of the demihyperoctahedral group D_n. We also give an idea for the deduction of irreducible representations of D_n from that of B_n. In Appendix B, we consider a random walk on D_n analogous to the flip-transpose top with random shuffle on B_n and show that this random walk exhibits the total variation cutoff phenomenon with cutoff at (n-1/2)log n.



 §.§ Acknowledgement
 I would like to thank my advisor Arvind Ayyer for proposing the problem and for all the insightful discussions during the preparation of this paper. I would like to thank the anonymous referee for the suggestion that simplifies the proof of the lower bound. I would like to acknowledge support in part by a UGC Centre for Advanced Study grant.



§ SPECTRUM OF THE TRANSITION MATRIX P(R)

In this section, we find the eigenvalues of the transition matrix P(R), the Fourier transform of P at the right regular representation R of B_n. To find the eigenvalues of P(R), we will use the representation theory of the hyperoctahedral group B_n. We briefly discuss the representation theory of B_n. For more details, one can see <cit.>. 

A partition λ of a positive integer n is denoted by λ⊢ n and is defined by a finite sequence of positive integers (λ_1,λ_2,…,λ_ℓ) satisfying λ_1≥λ_2≥…≥λ_ℓ>0 and |λ|:=∑_i=1^ℓλ_i=n. The Young diagram of shape λ is an arrangement of n boxes into ℓ rows in a left justified way such that the ith row contains λ_i boxes for 1≤ i≤ℓ. We use the same notation λ to express both the partition and the Young diagram. The content of a box in row i and column j of a Young diagram is the integer j-i. Given a Young diagram λ, its conjugate λ^' is obtained by reflecting λ with respect to the diagonal consisting of boxes with content 0. A standard Young tableau of shape λ is a filling of the boxes of the Young diagram of shape λ with the numbers 1,…,n such that the numbers are increasing along each row and each column. The set of all standard Young tableaux of shape λ is denoted by (λ), and the number of standard Young tableaux of shape λ is denoted by d_λ.



Let n be a positive integer. A (Young) double-diagram with n boxes μ is an (ordered) pair of Young diagrams such that the total number of boxes is n. We define ||μ||=n. The set of all double-diagrams with n boxes is denoted by . For example, the double-diagrams with 3 boxes are listed in Figure <ref>. A standard (Young) double-tableau of shape μ is obtained by taking the double-diagram μ and filling its ||μ|| boxes (bijectively) with the numbers 1,2,…,||μ|| such that the numbers in the boxes strictly increase along each row and each column of all Young diagrams occurring in μ. Let (n,μ), where μ∈, denote the set of all standard double-tableaux of shape μ and let (n)=μ∈∪(n,μ). For example an element of (8) is given in Figure <ref>. Let T∈(n,μ) and i∈[n]. Let b_T(i) be the box of the Young diagram in μ, in which the number i resides. We denote the content of the box b_T(i) by  c(b_T(i)). For the standard double-tableau given in Figure <ref>, we have c(b_T(1))=0, c(b_T(2))=1, c(b_T(3))=0, c(b_T(4))=1, c(b_T(5))=-1, c(b_T(6))=-1, c(b_T(7))=0, c(b_T(8))=2.



The Young-Jucys-Murphy elements X_1,X_2,…,X_n of ℂ[B_n] are defined by X_1= 0 and X_i= ∑_k=1^i-1(k,i)+∑_k=1^i-1(-k,i), for all 2≤ i≤ n.


Let μ∈B_n (set of all irreducible representations of B_n) and consider the B_n-module V^μ. Since the branching is simple <cit.>, the decomposition into irreducible B_n-1-modules is canonical and is given by 

    V^μ=λ⊕V^λ,

where the sum is over all λ∈B_n-1, with λ↗μ (i.e. there is an edge from λ to μ in the branching multi-graph). Iterating this decomposition of V^μ into irreducible B_1-modules, we obtain

    V^μ=T⊕v_T,

where the sum is over all possible chains T=μ_1↗μ_2↗…↗μ_n with μ_i∈B_i and μ_n=μ. We call (<ref>) the Gelfand-Tsetlin decomposition of V^μ and each v_T in (<ref>) a Gelfand-Tsetlin vector of V^μ. We note that if 0≠ v_T, then ℂ[B_i]v_T=V^μ_i. The Gelfand-Tsetlin vectors of V^μ form a basis of V^μ.

The irreducible representations of B_n are parametrised by elements of  <cit.>. We may index the Gelfand-Tsetlin vectors of V^μ by standard double-tableaux  of shape μ for μ∈ <cit.> and write the Gelfand-Tsetlin decomposition as 

    V^μ=T∈(n,μ)⊕v_T.

Let μ=(μ^(1),μ^(2))∈ and T∈(n,μ). Then the action <cit.> of the Young-Jucys-Murphy elements X_i and the signed permutation (i,-i) on v_T are given by 

    X_i  v_T    = 2c(b_T(i)) v_T for all i∈ [n],
    
     (-i,i)  v_T    =
     v_T   if b_T(i) is in μ^(1)
    
     -v_T   if b_T(i) is in μ^(2) for all i∈ [n].


		The components of the elements of  are indexed by the irreducible representations of the cyclic group of order two. In this paper, we adopt the convention that the first component of the elements of  is indexed by the trivial representation.

We now come to our main problem of finding the eigenvalues of the transition matrix P(R). The eigenvalues of P(R) are the eigenvalues of 1/2n(+(-n,n)+X_n) acting on ℂ[B_n] by multiplication on the right.
The following theorem gives the eigenvalues of P(R).
	
	For each μ=(μ^(1),μ^(2))∈ satisfying m:=|μ^(1)|∈{0,1,…,⌊n/2⌋}, let T∈(n,μ). Then c(b_T(n))+1/n and c(b_T(n))/n are eigenvalues of P(R) with multiplicity M(μ) each, where 
	
    M(μ)=  n md_μ^(1)d_μ^(2),   if 0≤ m < n/2,
    1/2n md_μ^(1)d_μ^(2),   if m= n/2 (when n is even).



For each μ=(μ^(1),μ^(2))∈, we have another double-diagram μ̃ with n boxes such that μ̃=(μ^(2),μ^(1)). We first find the eigenvalues of the matrix P(R) in the irreducible B_n-modules V^μ and V^μ̃. For each T=(T_1,T_2)∈(n,μ), T=(T_2,T_1)∈(n,μ̃). If b_T(n) is in μ^(1), then b_T(n) is in μ̃^(2). Without loss of generality, let us assume that b_T(n) is in μ^(1) and b_T(n) is in μ̃^(2). Let us recall v_T (respectively v_T) is the Gelfand-Tsetlin vector of V^μ (respectively V^μ̃).
From (<ref>) we have (-n,n) v_T= v_T  and X_n v_T= 2c(b_T(n)) v_T, which implies the following:

    (+(-n,n)+X_n) v_T=   (1+1+2c(b_T(n))) v_T
     =   (2c(b_T(n))+2) v_T.

Since {v_T: T∈(n,μ)} form a basis of V^μ, the eigenvalues of the action of (+(-n,n)+X_n) on V^μ can be obtained from (<ref>).
Now using (<ref>) again we have (-n,n) v_T=-v_T and X_n v_T= 2c(b_T(n)) v_T, thus

    (+(-n,n)+X_n) v_T=   (1-1+2c(b_T(n))) v_T
    
    =     2c(b_T(n)) v_T.

 Therefore the eigenvalues of the action of (+(-n,n)+X_n) on V^μ̃ are obtained from (<ref>), as {v_T: T∈(n,μ̃)} form a basis of V^μ̃.  
Thus considering the action of 1/2n(+(-n,n)+X_n) on V^μ and V^μ̃ simultaneously, the eigenvalues of P(R) are given by c(b_T(n))+1/n and c(b_T(n))/n for each T∈(n,μ). 

Now we know that the multiplicity of every irreducible representation in the right regular representation is equal to its dimension. Therefore the multiplicity of the eigenvalues are dim(V^μ)=n md_μ^(1)d_μ^(2)=dim(V^μ̃) if 0≤ m < n/2 and the multiplicity of the eigenvalues are 1/2n md_μ^(1)d_μ^(2) if m=n/2 (when n is even). The multiplicity of the eigenvalues for the case of m=n/2 is half of the dimension of the corresponding B_n-module because of the following: In this case m=n-m. Thus both μ=(μ^(1),μ^(2)) and μ̃=(μ^(2),μ^(1)) are in  such that their first component is a partition of m and the second component is a partition of n-m. Therefore while computing the eigenvalues of P(R) by considering the irreducible B_n-modules V^μ and V^μ̃, each space is counted twice. Now the proof of the theorem follows from the fact that all the irreducible representations of B_n are parameterised by .




§ UPPER BOUND OF TOTAL VARIATION DISTANCE

In this section, we will prove the theorem giving an upper bound of the total variation distance ||P^*k-U_B_n||_TV for k≥ nlog n+cn, c>0. Given a positive integer ℓ, throughout this section we write λ⊢ℓ to denote λ is a partition of ℓ. Let us recall that (λ) denote the set of all standard Young tableaux of shape λ.

Let p be a probability measure on a finite group  G such that p(x)=p(x^-1) for all x∈ G. Suppose the random walk on G driven by p is irreducible. Then we have the following

    ||p^*k-U_G||^2_TV≤1/4∑_ρ^*d_ρ((p(ρ))^2k),

where the sum is over all non-trivial irreducible representations  D_ρ of G and d_ρ is the dimension of D_ρ.


Let m be any positive integer satisfying 1≤ m≤n/2 and μ=(μ^(1), μ^(2))∈ be such that |μ^(1)|=m, |μ^(2)|=n-m. If μ^(i)_1 (respectively μ^(i)'_1) denotes the largest part of the partition μ^(i) (respectively its conjugate μ^(i)')  for i=1,2, then

    ∑_T∈(n,μ)(c(b_T(n))+x/n)^2k<n md_μ^(2)d_μ^(1)∑_i=1^2((μ^(i)_1/n)^2k+(μ^(i)'_1/n)^2k),

with x=0,1.


The set (n,μ) is a disjoint union of the sets 𝒯_1={(T_1,T_2)∈(n,μ):b_T(n) is in T_1} and 𝒯_2={(T_1,T_2)∈(n,μ):b_T(n) is in T_2}. 
Therefore we have

    ∑_T∈(n,μ)(c(b_T(n))+x/n)^2k=∑_T∈𝒯_1(c(b_T(n))+x/n)^2k+∑_T∈𝒯_2(c(b_T(n))+x/n)^2k.
 
Now the right hand side of (<ref>) is equal to

    n-1 n-md_μ^(2)∑_T_1∈(μ^(1))(c(b_T_1(m))+x/n)^2k+n-1 md_μ^(1)∑_T_2∈(μ^(2))(c(b_T_2(n-m))+x/n)^2k
       <n m(d_μ^(2)∑_T_1∈(μ^(1))(c(b_T_1(m))+x/n)^2k+d_μ^(1)∑_T_2∈(μ^(2))(c(b_T_2(n-m))+x/n)^2k)
       ≤n md_μ^(2)d_μ^(1)((μ^(1)_1/n)^2k+(μ^(1)'_1/n)^2k+(μ^(2)_1/n)^2k+(μ^(2)'_1/n)^2k).

The inequality in (<ref>) follows from the fact: If λ_1 (respectively λ_1^') denotes the largest part of the partition λ (respectively its conjugate λ^'), then for all T∈(λ) and for x=0,1 we have

    (c(b_T(|λ|))+x/n)^2k≤max{(λ_1-1+x/n)^2k,(λ_1^'-1-x/n)^2k}<(λ_1/n)^2k+(λ_1^'/n)^2k.



Let ℓ be a positive integer. For a partition λ of ℓ, if λ_1 denotes the largest part of λ, then

    ∑_λ⊢ℓd_λ^2(λ_1/ℓ)^2k<e^ℓ^2e^-2k/ℓ.



For any partition ζ of ℓ-λ_1 with largest part ζ_1 less than or equal to λ_1, we have d_λ≤ℓλ_1d_ζ. Therefore ∑_λ⊢ℓd_λ^2(λ_1/ℓ)^2k is less than or equal to

    ∑_λ_1=1^ℓ ∑_ζ⊢(ℓ-λ_1)
    ζ_1≤λ_1ℓλ_1^2d_ζ^2(λ_1/ℓ)^2k   ≤∑_λ_1=1^ℓℓλ_1^2(λ_1/ℓ)^2k∑_ζ⊢(ℓ-λ_1)d_ζ^2
       =∑_λ_1=1^ℓℓℓ-λ_1^2(ℓ-λ_1)!(1-ℓ-λ_1/ℓ)^2k.

Now writing t=ℓ-λ_1 and using 1-x≤ e^-x for x≥ 0, the expression in (<ref>) less than or equal to ∑_t=0^ℓ-1ℓ t^2t!e^-2kt/ℓ. Thus we have

    ∑_λ⊢ℓd_λ^2(λ_1/ℓ)^2k≤∑_t=0^ℓ-1ℓ t^2t!e^-2kt/ℓ   =∑_t=0^ℓ-1(ℓ(ℓ-1)…(ℓ-t+1))^2/t!e^-2kt/ℓ
       ≤∑_t=0^ℓ-1(ℓ^2e^-2k/ℓ)^t/t!<e^ℓ^2e^-2k/ℓ.



We know that the trace of the (2k)th power of a matrix is the sum of the (2k)th powers of its eigenvalues. Therefore Lemma <ref> implies 4||P^*k-U_B_n||^2_TV is bounded above by the sum of (2k)th powers of the non-largest eigenvalues (which are strictly less the largest eigenvalue 1) of P(R).
Thus from Theorem <ref>, we have

    4||P^*k-U_B_n||^2_TV   ≤(n-1/n)^2k+∑_λ⊢ n
    λ≠(n)d_λ(∑_T∈(λ)((c(b_T(n))+1/n)^2k+(c(b_T(n))/n)^2k))
    
    +   ∑_m=1^⌊n/2⌋∑_μ^(1)⊢ m
    μ^(2)⊢ (n-m)
    μ=(μ^(1), μ^(2))M(μ)(∑_T∈(n,μ)((c(b_T(n))+1/n)^2k+(c(b_T(n))/n)^2k)).

M(μ) is defined in (<ref>) and can be written as M(μ)=𝕀(n,m)n md_μ^(1)d_μ^(2), where

    𝕀(n,m)=
    1   if 0≤ m < n/2,
    1/2   if m= n/2 (when n is even).

 Using Lemma <ref>, the third term in the right hand side of (<ref>) is less than the following expression

    ∑_m=1^⌊n/2⌋∑_μ^(1)⊢ m
    μ^(2)⊢ (n-m)
    μ=(μ^(1), μ^(2))2M(μ)n md_μ^(2)d_μ^(1)∑_i=1^2((μ^(i)_1/n)^2k+(μ^(i)'_1/n)^2k)
       =2∑_m=1^⌊n/2⌋∑_μ^(1)⊢ m
    μ^(2)⊢ (n-m)
    μ=(μ^(1), μ^(2))2M(μ)n md_μ^(2)d_μ^(1)((μ^(1)_1/n)^2k+(μ^(2)_1/n)^2k)
       =4∑_m=1^⌊n/2⌋𝕀(n,m)n m^2∑_μ^(1)⊢ m
    μ^(2)⊢ (n-m)d_μ^(1)^2d_μ^(2)^2((μ^(1)_1/n)^2k+(μ^(2)_1/n)^2k)
       =4∑_m=1^⌊n/2⌋𝕀(n,m)n m^2((n-m)!∑_μ^(1)⊢ md_μ^(1)^2(μ^(1)_1/n)^2k+m!∑_μ^(2)⊢ (n-m)d_μ^(2)^2(μ^(2)_1/n)^2k).

The equality in (<ref>) holds because
	
    ∑_μ^(1)⊢ m
    μ^(2)⊢ (n-m)
    μ=(μ^(1), μ^(2))2M(μ)n md_μ^(2)d_μ^(1)(μ^(i)'_1/n)^2k=∑_μ^(1)⊢ m
    μ^(2)⊢ (n-m)
    μ=(μ^(1), μ^(2))2M(μ)n md_μ^(2)d_μ^(1)(μ^(i)_1/n)^2k

for i=1,2. Now the definition of 𝕀(n,m) and  
    ∑_m=1^⌊n/2⌋𝕀(n,m)n m^2 m!∑_μ^(2)⊢ (n-m)d_μ^(2)^2(μ^(2)_1/n)^2k=∑_t=⌈n/2⌉^n-1𝕀(n,n-t)n n-t^2 (n-t)!∑_μ^(2)⊢ td_μ^(2)^2(μ^(2)_1/n)^2k

implies that the expression (<ref>) is equal to

    4∑_m=1^n-1n m^2(n-m)!∑_μ^(1)⊢ md_μ^(1)^2(μ^(1)_1/n)^2k.

Replacing ℓ (respectively λ) by m (respectively μ^(1)) in Lemma <ref>, we have ∑_μ^(1)⊢ md_μ^(1)^2(μ^(1)_1/m)^2k<e^m^2e^-2k/m. Thus ∑_μ^(1)⊢ md_μ^(1)^2(μ^(1)_1/m)^2k< e, if k≥ mlog m. Therefore when k≥ nlog n (which implies k≥ mlog m), the expression in (<ref>) and hence the third term in the right hand side of (<ref>) is less than

    4e∑_m=1^n-1n m^2(n-m)!(m/n)^2k= 4e∑_t=1^n-1n t^2t!(1-t/n)^2k   < 4e∑_t=1^n-1(n^2e^-2k/n)^t/t!
       <4e(e^n^2e^-2k/n-1).

Now we consider the second term in the right hand side of (<ref>). The second term in the right hand side of (<ref>) is bounded above by

    2∑_λ⊢ n
    λ≠ (n),(1^n)d_λ^2((λ_1/n)^2k+(λ_1^'/n)^2k)+(n-2/n)^2k+(n-1/n)^2k.

Now using ∑_λ⊢ n
λ≠ (n),(1^n)d_λ^2(λ_1^'/n)^2k=∑_λ⊢ n
λ≠ (n),(1^n)d_λ^2(λ_1/n)^2k, the expression in (<ref>) is equal to

    4   ∑_λ⊢ n
    λ≠ (n),(1^n)d_λ^2(λ_1/n)^2k+(1-2/n)^2k+(1-1/n)^2k
    
    <    4(∑_λ⊢ nd_λ^2(λ_1/n)^2k-1)+e^-4k/n+e^-2k/n.

The right hand side of the expression (<ref>) and hence the second term in the right hand side of (<ref>) is less than 4(e^n^2e^-2k/n-1)+e^-4k/n+e^-2k/n by Lemma <ref>. Thus the inequality (<ref>) becomes

    4||P^*k-U_B_n||^2_TV≤ 2e^-2k/n+(4+4e)(e^n^2e^-2k/n-1)+e^-4k/n,  for k≥ nlog n.

Now if k≥ nlog n+cn and c>0, then the right hand side of (<ref>) becomes

    (4e+4)(e^e^-2c-1)+2e^-2c/n^2+e^-4c/n^4<(8e+8)e^-2c+o(1).

This proves the first part of the theorem. Now for ϵ∈(0,1), k_n=⌊(1+ϵ)n log n⌋ implies, k_n≥(1+ϵ)n log n. Thus the right hand side of (<ref>) is bounded above by 

    (4e+4)(e^1/n^2ϵ-1)+2n^-2(1+ϵ)+n^-4(1+ϵ).
 
Therefore the proof of the second part follows from

    lim_n→∞(4e+4)(e^1/n^2ϵ-1)+2/n^2(1+ϵ)+1/n^4(1+ϵ)=0.





§ LOWER BOUND OF TOTAL VARIATION DISTANCE

In this section, we will find a lower bound of the total variation distance ||P^*k-U_B_n||_TV for k=log n+cn, c≪0. We define a group homomorphism from B_n onto the symmetric group S_n which projects the flip-transpose top with random shuffle on B_n to the transpose top with random shuffle on S_n. We begin with a variant of the transpose top with random shuffle on S_n. This will be useful in obtaining the lower bound of ||P^*k-U_B_n||_TV.

Given 0<a<1, we define a probability measure 𝒫_a on the symmetric group S_n as follows:

    𝒫_a(π)=
    a    if π=s_, the identity element of S_n,
    1-a/n-1    if π=s_(i,n), 1≤ i<n,
         for π∈ S_n,

where s_(i,n) denotes the transposition in S_n interchanging i and n. We prove a theorem which provides a lower bound of ||𝒫_a^*k-U_S_n||_TV. Although the proof is straightforward and uses techniques <cit.> from the transpose top with random shuffle on S_n, we prove it to make this paper self contained. Recall that 𝒫_a(R) denotes the Fourier transform of 𝒫_a at the right regular representation R of S_n. Thus 𝒫_a(R) is the transition matrix for the random walk on S_n driven by 𝒫_a (since 𝒫_a(R) is symmetric). If we denote the nth Young-Jucys-Murphy element of ℂ[S_n] using notation X_n', then 𝒫_a(R) is the action of as_+1-a/n-1X_n' on ℂ[S_n] by multiplication on the right. Moreover given an irreducible S_n-module (Specht module) S^λ indexed by λ⊢ n, the actions of X_n' on the Gelfand-Tsetlin basis vectors of S^λ are given as follows: X_n'(u_T)=c(b_T(n))u_T, where u_T denotes the Gelfand-Tsetlin basis vector of S^λ indexed by T∈(λ) and recall that c(b_T(n)) is the content of the box containing n in T <cit.>. Let us define a random variable 𝔣 on S_n given as follows:

    𝔣(π):=numbers of fixed points of π,  for π∈ S_n.

The expected value of 𝔣 with respect to the uniform distribution U_S_n is given by E_U(𝔣)=1 <cit.>. Moreover if 𝒫_a(R)|_λ denotes the restriction of 𝒫_a(R) to the irreducible S_n-module S^λ, then the expected value of 𝔣 with respect to the distribution 𝒫_a^*k is given by

    E_a,k(𝔣)   =((𝒫_a(R)|_(n))^k)+((𝒫_a(R)|_(n-1,1))^k),<cit.>
       =1+(n-2)(1-1-a/n-1)^k+(an-1/n-1)^k,  see Table <ref>
       ≈1+(n-2)e^-(1-a/n-1)k+(an-1/n-1)^k.

Here ` ≈' means `asymptotic to' i.e. a_n≈ b_n means lim_n→∞a_n/b_n=1.
The expectation of 𝔣^2 with respect to the distribution 𝒫_a^*k is given by

    E_a,k(𝔣^2)   =2((𝒫_a(R)|_(n))^k)+3((𝒫_a(R)|_(n-1,1))^k)
         +((𝒫_a(R)|_(n-2,2))^k)+((𝒫_a(R)|_(n-2,1,1))^k),<cit.>
       =2+3((n-2)(1-1-a/n-1)^k+(an-1/n-1)^k)
         +((n-1)(n-4)/2(1-2(1-a)/n-1)^k+(n-2)a^k)
         +((n-2)(n-3)/2(1-2(1-a)/n-1)^k+(n-2)(an+a-2/n-1)^k),  see Table <ref>
       ≈2+3(n-2)e^-(1-a/n-1)k+(n^2-5n+5)e^-2(1-a/n-1)k
            +3(an-1/n-1)^k+(n-2)(a^k+(an+a-2/n-1)^k).




	For the random walk on S_n driven by 𝒫_a, we have the following:
	
    ||𝒫_a^*k-U_S_n||_TV≥ 1-4(E_a,k(𝔣^2)-(E_a,k(𝔣))^2)/(E_a,k(𝔣))^2-2/E_a,k(𝔣),

	where E_a,k(𝔣) and E_a,k(𝔣^2) are given in (<ref>) and (<ref>) respectively.


	If _a,k(𝔣) denotes the variance of 𝔣 with respect to the probability measure 𝒫_a^*k, then Chebychev's inequality implies that
	
    𝒫_a^*k({π∈ S_n: |𝔣(π)-E_a,k(𝔣)|≤E_a,k(𝔣)/2})≥1-4_a,k(𝔣)/(E_a,k(𝔣))^2.

	Again using 𝔣≥ 0, E_U(𝔣)=1 and the Markov's inequality, we have
	
    U_S_n({π∈ S_n: 𝔣(π)≥E_a,k(𝔣)/2})    ≤2E_U(𝔣)/E_a,k(𝔣)=2/E_a,k(𝔣).

	Now from the definition of total variation distance, we have
	
    ||𝒫_a^*k-U_S_n||_TV   =sup_A⊂ S_n|𝒫_a^*k(A)-U_S_n(A)|
       ≥𝒫_a^*k({π∈ S_n: |𝔣(π)-E_a,k(𝔣)|≤E_a,k(𝔣)/2})
         -U_S_n({π∈ S_n: |𝔣(π)-E_a,k(𝔣)|≤E_a,k(𝔣)/2})
    
    	   ≥𝒫_a^*k({π∈ S_n: |𝔣(π)-E_a,k(𝔣)|≤E_a,k(𝔣)/2})
         -U_S_n({π∈ S_n: 𝔣(π)≥E_a,k(𝔣)/2}).

	Therefore the proposition follows from (<ref>), (<ref>), (<ref>), and the definition of variance.

We now come back to our main objective of this section i.e., computation of a lower bound of ||P^*k-U_B_n||_TV. Let us define a homomorphism f from B_n onto S_n as follows: For π∈ B_n,

    f: π↦(f(π):i↦|π(i)|, for 1≤ i≤ n).

i.e., f(π)∈ S_n sends i to |π(i)| for 1≤ i≤ n. Here |π(i)| denotes the absolute value of π(i). It can be checked that the mapping f defined in (<ref>) is a homomorphism (this follows directly by considering B_n as the wreath product S_2≀ S_n). The surjectivity of f follows from the definition. The homomorphism f projects the flip-transpose top with random shuffle on B_n to the transpose top with random shuffle on S_n i.e., Pf^-1=𝒫_1/n. We now prove a lemma which will be useful in proving the main result of this section.

	Although we prove the upcoming lemma for the probability distribution P on B_n, it is true if P is replaced by any other probability distribution on B_n.


	For any positive integer k we have (Pf^-1)^*k=P^*kf^-1.


	We use the first principle of mathematical induction on k. The base case for k=1 is true by definition. Now assume the induction hypothesis i.e., (Pf^-1)^*m=P^*mf^-1 for some positive integer m>1. Let π∈ S_n be chosen arbitrarily. Then for the inductive step k=m+1 we have the following:
	
    (Pf^-1)^*(m+1)(π)   =((Pf^-1)*(Pf^-1)^*m)(π)
       =∑_{ξ,ζ∈ S_n: ξζ=π}(Pf^-1)(ξ)(Pf^-1)^*m(ζ)
       =∑_{ξ,ζ∈ S_n: ξζ=π}(Pf^-1)(ξ)(P^*mf^-1)(ζ),  by the induction hypothesis,
       =∑_ξ,ζ∈ S_n
    ξζ=πP(f^-1(ξ))P^*m(f^-1(ζ))
       =∑_ξ,ζ∈ S_n
    ξζ=π∑_ξ^'∈ f^-1(ξ)
    ζ^'∈ f^-1(ζ)P(ξ^')P^*m(ζ^').

	Now using the fact that f is a homomorphism, we have the following:
	
    {(ξ^',ζ^')∈ f^-1(ξ)× f^-1(ζ): ξ,ζ∈ S_n and ξζ=π}={(ξ^',ζ^')∈ B_n× B_n: ξ^'ζ^'∈ f^-1(π)}.

	Therefore the expression in (<ref>) becomes
	
    ∑_{ξ^',ζ^'∈ B_n: ξ^'ζ^'∈ f^-1(π)}P(ξ^')P^*m(ζ^')   =∑_π^'∈ f^-1(π)∑_ξ^',ζ^'∈ B_n
    ξ^'ζ^'=π^'P(ξ^')P^*m(ζ^')
       =∑_π^'∈ f^-1(π)P^*(m+1)(π^')=(P^*(m+1)f^-1)(π).

	Thus the lemma follows from the first principle of mathematical induction.


	We know that, given two probability distributions μ and ν on Ω and a mapping ψ:Ω→Λ, we have ||μ-ν||_TV≥ ||μψ^-1-νψ^-1||_TV, where Λ is finite <cit.>. Therefore we have the following:
	
    ||P^*k-U_B_n||_TV   ≥||P^*kf^-1-U_B_nf^-1||_TV
       =||(Pf^-1)^*k-U_S_n||_TV,  by Lemma (<ref>) and U_B_nf^-1=U_S_n,
       =||𝒫_1/n^*k-U_S_n||_TV,  using Pf^-1=𝒫_1/n.

	Now setting a=1/n in (<ref>) and (<ref>) we have
	
    E_1/n,k(𝔣)   ≈ 1+(n-2)e^-k/n.
    
    	E_1/n,k(𝔣^2)   ≈  2+3(n-2)e^-k/n+(n^2-5n+5)e^-2k/n+(n-2)(1+(-1)^k/n^k).

	Therefore Proposition <ref> and (<ref>) implies that
	
    ||P^*k-U_B_n||_TV≥   1-2(3+3(n-2)e^-k/n-2(n-1)e^-2k/n+o(1))/(1+(n-2)e^-k/n)^2,  for k>1.

	Now if n is large, c≪0 and k=nlog n+cn, then by (<ref>), we have the first part of this theorem.
	Again for any ϵ∈ (0,1) and k_n=⌊(1-ϵ)nlog n⌋ from (<ref>), we have
	
    1≥ ||P^*k_n-U_B_n||_TV≥  1-2(3+3n^ϵ+o(1)(n^2ϵ+n^ϵ+1))/(1+(1+o(1))n^ϵ)^2,

	for large n. Therefore, the second part of this theorem follows from (<ref>) and the fact that
	
    lim_n→∞2(3+3n^ϵ+o(1)(n^2ϵ+n^ϵ+1))/(1+(1+o(1))n^ϵ)^2=0.


Therefore from the first part of Theorems <ref> and <ref>, we can say that the mixing time for the 
flip-transpose top with random shuffle on B_n is O(nlog n) (i.e., order of nlog n). Furthermore, the second part of Theorems <ref> and <ref> implies that this shuffle satisfies the cutoff phenomenon and the total variation cutoff for this shuffle occurs at nlog n.

	Let 0≤α≤ 1. A generalisation of the flip-transpose top with random shuffle on B_n can be considered, which we call the biased flip-transpose top with random shuffle on B_n. Given an arrangement of n distinct oriented cards in a row, choose a card uniformly at random and choose the last card. Then perform one of the following moves:
	
		
  * Transpose the chosen cards with probability α/2.
		
  * Transpose the chosen cards after flipping both the cards with probability α/2.
		
  * Transpose the chosen cards after flipping one of the cards with probability 1-α/2.
	
This is the random walk on B_n driven by the probability measure P_α on B_n, defined below.

    P_α(π)=
    1/n·α/2,   if π=(i,n) or (-i,n) for 1≤ i≤ n,  here (n,n):=,
    1/n·1-α/2,   if π=(-n,n)(i,n) or (-i,i)(i,n) for 1≤ i≤ n,
     0,   otherwise.

The Fourier transform P_α(R) of P_α at the right regular representation R is the transition matrix for this biased variant. Recall that the nth Young-Jucys-Murphy element of B_n is X_n. Then P_α(R) is the action of 1/2n(α+(1-α)(-n,n))(+(-n,n)+X_n) on ℂ[B_n] by multiplication on the right. It can be easily seen that P_α(R) and P(R) have the same set of eigenvectors when they act on the irreducible B_n-modules. Therefore using the arguments given in the proof of Theorem <ref>, we can obtain the eigenvalues of P_α(R) as follows: For each μ=(μ^(1),μ^(2))∈ satisfying m:=|μ^(1)|∈{0,1,…,⌊n/2⌋}, let T∈(n,μ). Then c(b_T(n))+1/n and c(b_T(n))/n(2α-1) are eigenvalues of P_α(R) with multiplicity M(μ) each. Now using the fact -1≤2α-1≤ 1, we can conclude that ||P^*k-U_B_n||_TV and ||P_α^*k-U_B_n||_TV have the same upper bound. Thus Theorem <ref> is true if P is replaced by P_α. Moreover, the same mapping f defined in (<ref>) projects the biased flip-transpose top with random shuffle on B_n to the transpose top with random shuffle on S_n. Therefore ||P^*k-U_B_n||_TV and ||P_α^*k-U_B_n||_TV have the same lower bound. Thus Theorem <ref> is true if P is replaced by P_α. Hence the biased flip-transpose top with random shuffle on B_n satisfies total variation cutoff phenomenon with cutoff time nlog n.




§ REPRESENTATION THEORY OF DEMIHYPEROCTAHEDRAL GROUP D_N

 In this section, we briefly discuss the irreducible representations of D_n (detailed proofs are omitted). Our main aim is to look at the restriction of the irreducible representations of B_n to D_n. 
 
Let us consider the one-dimensional character (or representation) ξ:B_n→({± 1}, ·) of B_n. The action of ξ on the generators of B_n is defined by

    ξ(π)=
    -1,    if π=(-1,1),
    
    1,    if π=(i,i+1) for  1≤ i ≤ n-1.

It can be easily seen that (ξ)=D_n and the B_n-module V⊗ξ is irreducible if and only if the B_n-module V is irreducible. We have already seen in Section <ref> that the irreducible representations of B_n are indexed by . If μ=(μ^(1),μ^(2))∈, then μ̃=(μ^(2),μ^(1))∈. Now from <cit.>, it follows that the irreducible B_n-modules V^μ⊗ξ and V^μ̃ are isomorphic for μ∈. 

For the irreducible B_n-module V^μ indexed by μ=(μ^(1),μ^(2))∈, we have the following:


  * If μ^(1)≠μ^(2), then the restriction V^μ↓^B_n_D_n of V^μ to D_n is irreducible as a D_n-module. We denote this irreducible D_n-module by the same notation V^μ. Moreover, if μ̃=(μ^(2),μ^(1)), then V^μ and V^μ̃ are isomorphic as D_n-modules. If ν∈ be such that ν≠μ and ν≠μ̃, then V^ν and V^μ are non-isomorphic as D_n-modules.

  * If μ^(1)=μ^(2), then the restriction V^μ↓^B_n_D_n of V^μ to D_n is a direct sum of two irreducible D_n-modules with the same dimension. We denote these irreducible D_n-modules by V^μ_+ and V^μ_-.



The proof follows by mimicking the steps of deducing the irreducible representations of A_n from that of S_n <cit.>. Here A_n denotes the alternating group. For this proof, B_n (respectively D_n) will play the role of S_n (respectively A_n), and ξ will play the role of the one-dimensional sign character of S_n.

Let 𝒮 be the collection of subsets Γ of  satisfying the following properties:


  * μ^(1)≠μ^(2) for each (μ^(1),μ^(2))∈Γ,

  * (μ^(2),μ^(1))∉Γ if and only if (μ^(1),μ^(2))∈Γ.

Let Γ_1 be a maximal element of the poset (𝒮,⊆) and 
Γ_2={(μ^(1),μ^(2))∈: μ^(1)=μ^(2)}. Then from Theorem <ref> and the observation

    ∑_μ∈Γ_1(dim(V^μ))^2+∑_μ∈Γ_2((dim(V^μ_+))^2+(dim(V^μ_-))^2)
       =1/2(2∑_μ∈Γ_1(dim(V^μ))^2+∑_μ∈Γ_2(dim(V^μ))^2)=|B_n|/2=|D_n|,

all the irreducible D_n-modules are given by {V^μ:μ∈Γ_1}∪{V^μ_+,V^μ_-:μ∈Γ_2}. 


§ A RANDOM WALK ON D_N ANALOGOUS TO THE WALK ON B_N DRIVEN BY P

Let us consider the random walk on the demihyperoctahedral group D_n driven by the probability measure Q on D_n defined as follows:

    Q(π)=
    1/2n-1,   if π=, the identity element of D_n,
    1/2n-1,   if π=(i,n) for 1≤ i≤ n-1,
    1/2n-1,   if π=(-i,n) for 1≤ i≤ n-1,
    
    0,   otherwise.

It can be easily seen that the support of Q generates D_n and hence this random walk is irreducible. Moreover, this random walk is aperiodic too. Thus the distribution after kth transition for this random walks will converge to U_D_n as k→∞. Let us recall that Q(R) is the Fourier transform of Q at the right regular representation R of D_n. The transition matrix for the random walk on D_n driven by Q is the transpose of Q(R). To find the eigenvalues of Q(R) we will use the representation theory of D_n.

The eigenvalues of Q(R) are given by


  * If μ=(μ^(1),μ^(2))∈Γ_1, then for each T∈(n,μ), 2c(b_T(n))+1/2n-1 is an eigenvalue of Q(R) with multiplicity dim(V^μ).

  * If μ=(μ^(1),μ^(2))∈Γ_2, then for each T∈(n,μ), 2c(b_T(n))+1/2n-1 is an eigenvalue of Q(R) with multiplicity 1/2dim(V^μ).
 
Recall c(b_T(n)) is the content of the box containing n in T. 


We have Q(R)=1/2n-1(X_n+), where X_n is the nth Young-Jucys-Murphy element of B_n and  is the identity element of D_n. Here we identify the elements of D_n(⊆ B_n) by the elements of B_n.

For μ=(μ^(1),μ^(2))∈Γ_1, we have μ^(1)≠μ^(2). Therefore the restriction of irreducible B_n-module V^μ to D_n is irreducible (Theorem <ref>). Now for each T∈(n,μ), let v_T be the Gelfand-Tsetlin vector of V^μ satisfying X_nv_T=2c(b_T(n))v_T. Also, we know that {v_T:T∈(n,μ)} forms a basis of V^μ. Therefore the eigenvalues of Q(R) on the irreducible D_n-module V^μ are given by 2c(b_T(n))+1/2n-1 for each T∈(n,μ). Since the multiplicity of every irreducible representation in the right regular representation is equal to its dimension, therefore the multiplicity of these eigenvalues are dim(V^μ).

Now for μ=(μ^(1),μ^(2))∈Γ_2 we  have μ^(1)=μ^(2). Then the restriction of the irreducible B_n-module V^μ to D_n splits into two irreducible D_n-modules V^μ_+ and V^μ_- (Theorem <ref>). In this case also v_T is the Gelfand-Tsetlin vector of V^μ and {v_T:T∈(n,μ)} forms a basis of V^μ_+⊕ V^μ_-. Therefore, by similar arguments in case of μ^(1)≠μ^(2), the eigenvalues of Q(R) on the irreducible D_n-modules V^μ_+ and V^μ_- are given by 2c(b_T(n))+1/2n-1 for each T∈(n,μ). The multiplicity of these eigenvalues are 1/2dim(V^μ) ( ∵ dim(V^μ_+)=dim(V^μ_-)=1/2dim(V^μ)).


For the random walk on D_n driven by Q, we have the following:


  * ||Q^*k-U_D_n||_TV<√(e+1) e^-c+o(1), for k≥(n-1/2)(log n+c) and c>0.

  * lim_n→∞||Q^*k_n-U_D_n||_TV=0, for any ϵ∈ (0,1) and k_n=⌊(1+ϵ)(n-1/2)log n⌋.



Using Lemma <ref> and following similar steps of Theorem <ref>, we have 

    4||Q^*k-U_D_n||^2_TV≤ 2(1+e)(e^n^2e^-4k/2n-1-1)+e^-4k/2n-1,  for k≥(n-1/2)log n.

Now if k≥(n-1/2)(log n+c) and c>0, then the right hand side of (<ref>) becomes

    2(e+1)(e^e^-2c-1)+e^-2c/n^2<(4e+4)e^-2c+o(1).

This proves the first part of the theorem. Now for ϵ∈(0,1), k_n=⌊(1+ϵ)(n-1/2)log n⌋ implies, k_n≥(1+ϵ)(n-1/2)log n. Thus the right hand side of (<ref>) is bounded above by 2(e+1)(e^1/n^2ϵ-1)+1/n^2(1+ϵ). Therefore the proof of the second part follows from

    lim_n→∞2(e+1)(e^1/n^2ϵ-1)+1/n^2(1+ϵ)=0.


Now we obtain a lower bound for the total variation distance ||Q^*k-U_D_n||_TV. Recall the homomorphism f defined in (<ref>) and set f^'=f|_D_n, the restriction of f to D_n. Then f^' projects the random walk on D_n driven by Q to the random walk on S_n driven by 𝒫_1/2n-1. Thus we have U_D_nf^'-1=U_S_n and Qf^'-1=𝒫_1/2n-1. Now using the arguments used in the proof of Lemma <ref>, we can conclude that 
    𝒫_1/2n-1^*k=(Qf^'-1)^*k=Q^*kf^'-1.

Therefore using <cit.>, we have the following:

    ||Q^*k-U_D_n||_TV≥||Q^*kf^'-1-U_D_nf^'-1||_TV=||𝒫_1/2n-1^*k-U_S_n||_TV.


	For the random walk on D_n driven by Q, we have the following:
	
		
  * For large n, ||Q^*k-U_D_n||_TV≥ 1-2(3+3e^-c+o(1)(e^-2c+e^-c+1))/(1+(1+o(1))e^-c+o(1))^2, when k=(n-1/2)(log n+c) and c≪0.
		
  * lim_n→∞||Q^*k_n-U_D_n||_TV=1, for any ϵ∈ (0,1) and k_n=⌊(1-ϵ)(n-1/2)log n⌋.
	


	 Setting a=1/2n-1 in (<ref>) and (<ref>) we have 
	
    E_1/2n-1,k(𝔣)   ≈ 1+(n-2)e^-2k/2n-1+(-1/2n-1)^k.
    
    	E_1/2n-1,k(𝔣^2)   ≈ 2+3(n-2)e^-2k/2n-1+(n^2-5n+5)e^-4k/2n-1
           +3(-1/2n-1)^k+(n-2)((1/2n-1)^k+(-3/2n-1)^k).

	Therefore Proposition <ref> and (<ref>) implies that
	
    ||Q^*k-U_D_n||_TV≥ 1-2(3+3(n-2)e^-2k/2n-1-2(n-1)e^-4k/2n-1+o(1))/(1+(n-2)e^-2k/2n-1+o(1))^2,  for k>1.

	Now if n is large, c≪0 and k=(n-1/2)(log n+c), then by (<ref>), we have the first part of this theorem. Again for any ϵ∈ (0,1) and k_n=⌊(1-ϵ)(n-1/2)log n⌋ from (<ref>), we have
	
    1≥ ||Q^*k_n-U_D_n||_TV≥  1-2(3+3n^ϵ+o(1)(n^2ϵ+n^ϵ+1))/(1+(1+o(1))n^ϵ+o(1))^2

	for large n. Therefore, the second part of this theorem follows from (<ref>) and the fact that
	
    lim_n→∞2(3+3n^ϵ+o(1)(n^2ϵ+n^ϵ+1))/(1+(1+o(1))n^ϵ+o(1))^2=0.


Therefore from the first part of Theorems <ref> and <ref>, we can say that the mixing time for the random walk on D_n driven by Q is O((n-1/2)log n). Furthermore, the second part of Theorems <ref> and <ref> implies that this shuffle satisfies the cutoff phenomenon and the total variation cutoff for this shuffle occurs at (n-1/2)log n.



plain
