IMSc Webinar
Total variation cutoff for random walks on some finite groups
Subhajit Ghosh
IISc, Bangalore
Webinar link: us02web.zoom.us/j/87333756909
The random walk on the alternating group: We investigate the properties of a random walk on the
alternating group An generated by 3-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
obtain the sharp mixing time by proving the total variation cutoff phenomenon at (n − 3/2)log n for this
shuffle.
The random walk on the group of signed permutations: We consider a random walk on the hyperoctahedral
group Bn generated by the signed permutations of the form (i, n) and (−i, n) for 1 ≤ i ≤ n. We call this
the flip-transpose top with random shuffle on Bn. We find the spectrum of the transition probability
matrix for this shuffle. We prove that this shuffle exhibits the total variation cutoff phenomenon with
cutoff time n log n. Furthermore, we show that a similar random walk on the demihyperoctahedral
group Dn generated by the identity signed permutation and the signed permutations of the form (i, n) and
(−i, n) for 1 ≤ i < n also has a cutoff at (n − 1/2)log n.
The random walk on the complete monomial group: Let G1 ⊆ · · · ⊆ Gn ⊆ · · · be a sequence of finite groups
with |G1| > 2. We study the properties of a random walk on the complete monomial group Gn\wr Sn (wreath
product of Gn with Sn) generated by the elements of the form (e, . . . , e, g; id) and (e, . . . , e, g−1,
e, . . . , e, g; (i, n)) for g in Gn, 1 ≤ i < n. We call this the warp-transpose top with random shuffle
on Gn\wr Sn. We find the spectrum of the transition probability matrix for this shuffle. We show that this
shuffle satisfies cutoff phenomenon with cutoff time n log n if |Gn| = o( nδ ) for all δ > 0. We also
prove that the mixing time for this shuffle is of order n log n + (1/2) n log(|Gn| − 1).
Done