Mixing Times for the Commuting Chain on CA Groups
- PDF / 411,678 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 72 Downloads / 160 Views
Mixing Times for the Commuting Chain on CA Groups John Rahmani1 Received: 22 April 2020 / Revised: 20 August 2020 / Accepted: 16 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Let G be a finite group. The commuting chain on G moves from an element x to y by selecting y uniformly amongst those which commute with x. The t-step transition probabilities of this chain converge to a distribution uniform on the conjugacy classes of G. We provide upper and lower bounds for the mixing time of this chain on a CA group (groups with a “nice” commuting structure) and show that cutoff does not occur for many of these chains. We also provide a formula for the characteristic polynomial of the transition matrix of this chain. We apply our general results to explicitly study the chain on several sequences of groups, such as general linear groups, Heisenberg groups, and dihedral groups. The commuting chain is a specific case of a more general family of chains known as Burnside processes. Few instances of the Burnside processes have permitted careful analysis of mixing. We present some of the first results on mixing for the Burnside process where the state space is not fully specified (i.e., not for a particular group). Our upper bound shows our chain is rapidly mixing, a topic of interest for Burnside processes. Keywords Markov chains · Mixing times · Burnside process Mathematics Subject Classification (2020) 60J10
1 Introduction The commuting chain on a finite group G is a Markov chain with state space G which moves from x to y by selecting y uniformly amongst the elements which commute with x. The chain converges to an equilibrium distribution uniform on the conjugacy classes of G. Our aim in this paper is to study the mixing times (convergence rate) of this chain when G is a CA group. A group is a CA if upon removing the center commuting is a transitive relation (and thus partitions the group into equivalence classes of commuting elements).
B 1
John Rahmani [email protected] University of Southern California, Los Angeles, CA, USA
123
Journal of Theoretical Probability
Our main results are upper and lower bounds on mixing times of the commuting chain on a CA group in terms of the size of the group’s center and largest non-trivial centralizer. Using our upper bound, we are able to show that cutoff will not occur for this chain in many cases. We also provide a formula for characteristic polynomial for the transition matrix of this chain. Using that we see our bounds for mixing are better than what one obtains from using only the second largest eigenvalue. This chain is a an example of a more general family of chains known as Burnside processes introduced in [14] (see below for more). Some initial examples were shown to have rapid mixing, meaning the mixing time is bounded by a polynomial in the size of the state space. Later work ([13]) showed this will not always be the case for a Burnside process. Our main upper bound (Theorem 2.2) shows that the commuting chain is always rapidly m
Data Loading...
