Mixing times for the commuting chain on CA groups

DOI10.1007/S10959-020-01049-2zbMATH Open1484.60078arXiv2003.04432OpenAlexW3096349696MaRDI QIDQ2116487FDOQ2116487

John Rahmani

Publication date: 17 March 2022

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

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.

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)

Cites Work

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

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)