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

Markov chainsmixing timesBurnside process

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

• 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?)
• 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.
• Non-commuting graph of a group.
• Separation cut-offs for birth and death chains
• The cutoff phenomenon for ergodic Markov processes
• The ‘Burnside Process’ Converges Slowly
• Total variation cutoff in birth-and-death chains

Cited in

(1)

• Mixing times for random walks on finite lamplighter groups

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)