Total Variation Cutoff for the Transpose Top-2 with Random Shuffle
- PDF / 407,703 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 70 Downloads / 149 Views
Total Variation Cutoff for the Transpose Top-2 with Random Shuffle Subhajit Ghosh1 Received: 24 July 2018 / Revised: 5 June 2019 © Springer Science+Business Media, LLC, part of Springer Nature 2019
Abstract In this paper, we investigate the properties of a random walk on the alternating group An generated by three cycles of the form (i, n − 1, n) and (i, n, n − 1). We call this the transpose top-2 with random shuffle. We find the spectrum of the transition matrix of this shuffle. We show that the mixing time is of order n − 23 log n and prove that there is a total variation cutoff for this shuffle. Keywords Random walk · Alternating group · Mixing time · Cutoff · Jucys–Murphy elements Mathematics Subject Classification (2010) 60J10 · 60B15 · 60C05
1 Introduction The convergence of random walks on finite groups is a well-studied topic in probability theory. Under certain natural conditions, a random walk converges to a unique stationary distribution. The topic of interest, in this case, is the mixing time, i.e. the minimum number of steps the random walk takes to get close to its stationary distribution in the sense of total variation distance. To understand the convergence of random walks, it is helpful to know the eigenvalues and eigenvectors of the transition matrix. There is a large body of literature dealing with the convergence of random walks on the symmetric group. Random walks on the symmetric group can be practically described by shuffling of a deck of cards. Arrangements of this deck can be described by elements of the symmetric group. There are various types of shuffling algorithms of a deck of n-cards labelled from 1 to n. Shuffling problems on Sn can be generalised to other finite groups. One can take a look at [1–7] for various shuffles.
B 1
Subhajit Ghosh [email protected] Department of Mathematics, Indian Institute of Science, Bangalore 560 012, India
123
Journal of Theoretical Probability
This work is mainly motivated by the work of Flatto, Odlyzko and Wales [1], where they studied the transpose top with random shuffle on Sn (interchanging the top card with a random card). The eigenvalues for the transition matrix of the transpose top with random shuffle were obtained from the Jucys–Murphy elements for the symmetric group [8]. We consider an analogous variant called the transpose top- 2 with random shuffle on the alternating group. In this work, we will prove total variation cutoff for transpose top-2 with random shuffle on An . The transpose top-2 with random shuffle on An is a random walk on An driven by a probability measure P on An defined as follows: ⎧ 1 if π = id, ⎪ 2n−3 , ⎪ ⎪ ⎨ 1 , if π = (i, n − 1, n) for i ∈ {1, . . . , n − 2}, P(π ) = 2n−3 (1) 1 ⎪ , if π = (i, n, n − 1) for i ∈ {1, . . . , n − 2}, ⎪ ⎪ ⎩ 2n−3 0, otherwise. The distribution after k transitions is given by P ∗k (convolution of P with itself k times, details explanation will be given later in this section). Before stating the main result of this paper, we first define the total variation distance between two pro
Data Loading...
