Mixing times for the commuting chain on CA groups

DOI10.1007/S10959-020-01049-2MaRDI QIDQ2116487zbMATH OpenOpenAlexFDO

Authors John Rahmani

Publication date 17 March 2022

Published in Journal of Theoretical Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.04432

zbMATH Keywords

Burnside processMarkov chainsmixing times

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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.

Recommendations

• Mixing times for random \(k\)-cycles and coalescence-fragmentation chains
• scientific article; zbMATH DE number 1301969
• Mixing times for Markov chains on wreath products and related homogeneous spaces
• Cutoff for product replacement on finite groups
• Mixing and cut-off in cycle walks

Cites work

• Analysis of a Bose-Einstein Markov chain
• Analysis of a nonreversible Markov chain sampler.
• Characterization of cutoff for reversible Markov chains
• Groups in which commutativity is a transitive relation
• Hit and run as a unifying device
• Honest exploration of intractable probability distributions via Markov chain Monte Carlo.
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 1318047 (Why is no real title available?)
• scientific article; zbMATH DE number 475376 (Why is no real title available?)
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• Non-commuting graph of a group.
• Separation cut-offs for birth and death chains
• The ‘Burnside Process’ Converges Slowly
• The cutoff phenomenon for ergodic Markov processes
• Total variation cutoff in birth-and-death chains

Cited in

(7)

• Mixing times for random walks on finite lamplighter groups
• Limit profiles and cutoff for the Burnside process on Sylow double cosets
• Mixing times of a Burnside process Markov chain on set partitions
• Counting the number of group orbits by marrying the Burnside process with importance sampling
• Random sampling of contingency tables and partitions: two practical examples of the Burnside process
• An algorithm for uniform generation of unlabeled (Pólya) trees
• The dual Burnside process

This page was built for publication: Mixing times for the commuting chain on CA groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2116487)