Double coset Markov chains

DOI10.1017/FMS.2022.106MaRDI QIDQ5870344zbMATH OpenOpenAlexFDO

Authors Persi Diaconis, Arun Ram, Mackenzie Simper

Publication date 9 January 2023

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

double coset Markov chainsMallows stationary distributionMarkov chainrandom transvections walk

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Hecke algebras and their representations (20C08) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Let $G$ be a finite group. Let $H,K$ be subgroups of $G$ and $$ the double coset space. Let $Q$ be a probability on $G$ which is constant on conjugacy classes ($Q(s^{-1}ts)=Q(t)$). The random walk driven by $Q$ on $G$ projects to a Markov chain on $$. This allows analysis of the lumped chain using the representation theory of $G$. Examples include coagulation-fragmentation processes and natural Markov chains on contingency tables. Our main example projects the random transvections walk on $G{L}_n(q)$ onto a Markov chain on $S_n$ via the Bruhat decomposition. The chain on $S_n$ has a Mallows stationary distribution and interesting mixing time behavior. The projection illuminates the combinatorics of Gaussian elimination. Along the way, we give a representation of the sum of transvections in the Hecke algebra of double cosets. Some extensions and examples of double coset Markov chains with $G$ a compact group are discussed.

Recommendations

• scientific article; zbMATH DE number 2103163
• Examples of Markov chains on spaces with multiplicities
• Lifting Markov Chains to Random Walks on Groups
• Hypergroup deformations and Markov chains
• Lumpings of algebraic Markov chains arise from subquotients

Cites work

• \(q\)-rook monoid algebras, Hecke algebras, and Schur-Weyl duality.
• \(q\)-Whittaker functions, finite fields, and Jordan forms
• Algebraic algorithms for sampling from conditional distributions
• Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques
• Billiards in a general domain with random reflections
• Character levels and character bounds
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Comparison theorems for reversible Markov chains
• Complexity and randomness in the Heisenberg groups (and beyond)
• Compositions of random transpositions
• Cutoff for the Bernoulli-Laplace urn model with o(n) swaps
• Cutoff profile of ASEP on a segment
• Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists
• Folding actions
• Generating a random permutation with random transpositions
• Generating random elements in \(SL_ n(F_ q)\) by random transvections
• Harmonic analysis on finite groups. Representation theory, Gelfand pairs and Markov chains
• scientific article; zbMATH DE number 3854137 (Why is no real title available?)
• scientific article; zbMATH DE number 5544145 (Why is no real title available?)
• scientific article; zbMATH DE number 3725369 (Why is no real title available?)
• scientific article; zbMATH DE number 3739805 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 46141 (Why is no real title available?)
• scientific article; zbMATH DE number 193020 (Why is no real title available?)
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• scientific article; zbMATH DE number 1339030 (Why is no real title available?)
• scientific article; zbMATH DE number 1181673 (Why is no real title available?)
• scientific article; zbMATH DE number 2042290 (Why is no real title available?)
• scientific article; zbMATH DE number 2070153 (Why is no real title available?)
• Infinite-dimensional p-adic groups, semigroups of double cosets, and inner functions on Bruhat-Tits buildings
• Isotropic random walks in a tree
• Limit profile for random transpositions
• Lumpings of algebraic Markov chains arise from subquotients
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Matchings and phylogenetic trees
• Mixing times for random \(k\)-cycles and coalescence-fragmentation chains
• Monte Carlo strategies in scientific computing
• On the cycle structure of Mallows permutations
• Quasi-stationary distribution and metastability for the stochastic Becker-Döring model
• Random additions in urns of integers
• Random Fragmentation and Coagulation Processes
• Random generators of the symmetric group: diameter, mixing time and spectral gap.
• Refined estimates for some basic random walks on the symmetric and alternating groups
• Representation theory of finite groups and associative algebras.
• Representations of the infinite symmetric group
• Seminormal Representations of Weyl Groups and Iwahori-Hecke Algebras
• Small rank permutation representations of finite Chevalley groups
• Statistical enumeration of groups by double cosets
• Supercharacters, symmetric functions in noncommuting variables, and related Hopf algebras
• Symmetry Analysis of Reversible Markov Chains
• The algebra of elimination
• The cut-off phenomenon for random reflections
• The discrete coagulation-fragmentation equations: existence, uniqueness, and density conservation.
• The equilibrium behavior of reversible coagulation-fragmentation processes
• The gallery distance of flags
• The Subgroup Algorithm for Generating Uniform Random Variables
• What do we know about the Metropolis algorithm?

Cited in

(11)

• Lifting Markov Chains to Random Walks on Groups
• scientific article; zbMATH DE number 2103163 (Why is no real title available?)
• Examples of Markov chains on spaces with multiplicities
• A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle
• Counting Sylow double cosets in the symmetric group
• Random transpositions on contingency tables
• On the number and sizes of double cosets of Sylow subgroups of the symmetric group
• Lusztig varieties and Macdonald polynomials
• Probabilizing semigroups???
• Uniclass automorphisms of spherical buildings
• Genome rearrangements as double coset Markov chains

This page was built for publication: Double coset Markov chains

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