Cutoff for a one-sided transposition shuffle (Q2240867)

The aim of the paper under review is to prove the existence of a total-variation cutoff for the one-sided transposition shuffle (defined in this paper) at time \(n\log n\), and to explicitly give an formula for all eigenvalues of the shuffle by demonstrating a useful correspondence between eigenvalues and standard Young tableaux. \textit{P. Diaconis} and \textit{M. Shahshahani} [Z. Wahrscheinlichkeitstheor. Verw. Geb. 57, 159--179 (1981; Zbl 0485.60006)] first studied transposition shuffles using the representation theory of symmetry group \(S_n\), and showed that the random transposition shuffle in which the two positions are chosen independently and uniformly on \([n]\) via taking \((n/2)\log n\) steps to randomize the order of the deck. \textit{E. Mossel} et al. [``Shuffling by semi-random transpositions'', in: 45th Annual IEEE Symposium on Foundations of Computer Science. Los Alamitos, CA: IEEE Computer Society. 572--581 (2004)] formed an interesting class of Markov chains as semi-random transposition shuffles by choosing uniformly a card at random in the right hand and following independent stochastic process to choose a card in the left hand, and obtained a universal upper bound of \(O(n\log n)\) on the mixing time of any semi-random transposition shuffle. In the paper under review, authors define a new class of shuffles as one-sided transposition shuffles, i.e., at step \(i\) the right hand's position \((R^i)\) is chosen according to some arbitrary distribution on \([n]\) and given the value of \(R^i\) the distribution of the left hand's position \((L^i)\) is supported on the set \(\{1, \cdots, R^i\}\). The main result is that the one-sided transposition shuffle exhibits a cutoff at time \(t_n = n\log n\) in Theorem 3. The spectrum of the one-sided transposition shuffle is analyzed by using the representation theory of the symmetric group in Theorem 5. Section 1 Introduction gives the background and notations and terminologies as well as technical lemmas and Theorem 3 and Theorem 4. Section 2 focuses on the upper bound of Theorem 3 with review of Young diagram and standard Young Tableaux, where Lemma 8 shows how swapping numbers in a tableaux effects the corresponding eigenvalue, and Lemma 9 shows how eigenvalues behave after one move down the dominance order of partitions in the tableaux. Using Lemma 12.16 of [\textit{D. A. Levin} et al., Markov chains and mixing times. With a chapter on ``Coupling from the past'' by James G. Propp and David B. Wilson. Providence, RI: American Mathematical Society (AMS) (2009; Zbl 1160.60001)], the upper bound of Theorem 3 is to get the total variation distance in terms of the nontrivial eigenvalues of the transition matrix and the trivial eigenvalue corresponds to the one-dimensional partition \(\lambda = (n)\) by Lemma 6. This reduces to understand eigenvalues of any element of the set of standard Young tableaux of shape \(\lambda \) and the dimension \(d_{\lambda}\) of \(\lambda \), and to further reduce to decrease one move down the dominance order of partitions in the Young tableaux in Lemma 9 and Lemma 10. The upper bound on the sum of the squared dimension of all partitions with \(\lambda_1 = n-k\) is given by Corollary 2 of [Diaconis and Shahshahani, loc. cit.]. The dominant term in upper bound term (16) takes the form which tends to zero as \(n\to \infty\) by a straightforward application of Stirling's formula. Hence, the upper bound on the mixing time in Theorem 3 is proved by combining this result with previous upper bounds. Section 3 shows the lower bound of Theorem 3 on the mixing time by using the trick of finding a set of permutations \(B_n \subset S_n\) which has significantly different probability under the equilibrium distribution \(\pi_n\) and the one-sided transposition measure \(P_n^t\), \[ \|P_n^t - \pi_n\|_{TV} \ge P_n^t(B_n) - \pi_n (B_n). \] Since the left hand always choose a position below that of the right hand, one can focus on a set of positions at the top of the deck \(V_n =\{ n-n/m+1, \cdots, n-1, n\}\). The permutations \(B_n\) is the set of elements \(\rho \in S_n\) which has at least 1 fixed point in \(V_n\). Note that \(V_n\) contains \(n/m\) positions and \(\pi_n(B_n) \le 1/m\), and the problem to studying a simpler Markov chain linked to coupon collecting provides bound of \(P_n^t(B_n)\). With the help of Lemma 14, the lower bound in Theorem 3 follows. Section 4 gives a general result of Theorem 3 for biased one-sided transposition shuffles which allow the right hand to choose from a more general distribution on \([n]\). For the natural choice of weight function of the form \(w(j) =j^{\alpha}\) with \(\alpha \le 1\), Theorem 17 presents the biased one-sided transposition shuffle exhibits a total variation cutoff at time \(t_{n, \alpha} \log n\) for all \(\alpha \in R\). The proof of Theorem 17 follows from extensions of Section 2 and Section 3. Appendix provides lifting eigenvectors analysis by associate Specht module \(S^{\lambda} \) for each partition and \(\dim S^{\lambda} = d_{\lambda}\). Most materials of Appendix are from \textit{B. E. Sagan} [The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Pacific Grove, CA: Wadsworth \&| Brooks/Cole Advanced Books \&| Software (1991; Zbl 0823.05061)] and \textit{A. B. Dieker} and \textit{F. V. Saliola} [Adv. Math. 323, 427--485 (2018; Zbl 1405.60113)] to understand the Specht module, the switching operator, the adding operator on the permutation module \(M^{\lambda}\), the lifted eigenvetors form a basis of Specht module \(S^{\mu}\) for \(\mu -\lambda = e_a\) in Theorem 42, and Theorem 5 follows from the constructed basis in each Specht module, and the proof of Lemma 6 follows from labelling and keeping track of the changes in eigenvalue given in Theorem 49 of [Dieker and Saliola, loc. cit.]. There is a typo in the last page on Proof of Theorem 6, it should be Proof of Lemma 6.