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

Abstract

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\le i\le 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 $n\log 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 $\left(n-\frac{1}{2}\right)\log n$.

21 pages, 2 figures, 1 table. Minor revisions. The main results are stated in the introduction. Remarks 2.5 and 4.2 are added. Theorem 2.1 is rephrased. Corrections are made in Section 3. The proof of the lower bound is simplified using probabilistic techniques, thanks to an anonymous referee of ALEA Lat. Am. J. Probab. Math. Stat. for the suggestion. Few minor changes are done in Theorem B.2

References in corpus (1)

• Spectral gap for random-to-random shuffling on linear extensions

Cited by in corpus (1)

• Cutoff phenomenon for the warp-transpose top with random shuffle