Markov chains on Weyl groups from the geometry of the flag variety

2025/10/02 by Persi Diaconis, Diaconis, Persi, Calder Morton-Ferguson +1 · 1 citation
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Geometric and Algebraic Topology #advanced mathematical theories

paper · pdf · doi:10.48550/arxiv.2510.02285

Abstract

This paper studies a basic Markov chain, the Burnside process, on the space of flags G/B with G = GL_n(\mathbbF_q) and B its upper triangular matrices. This gives rise to a shuffling: a Markov chain on the symmetric group realized via the Bruhat decomposition. Actually running and describing this Markov chain requires understanding Springer fibers and the Steinberg variety. The main results give a practical algorithm for all n and q and determine the limiting behavior of the chain when q is large. In describing this behavior, we find interesting connections to the combinatorics of the Robinson-Schensted correspondence and to the geometry of orbital varieties. The construction and description is then carried over to finite Chevalley groups of arbitrary type, describing a new class of Markov chains on Weyl groups.

Citations

• A curiously slowly mixing Markov chain
• Estimating the size of a set using cascading exclusion
• Random sampling of contingency tables and partitions: Two practical examples of the Burnside process
• An algorithm for uniform generation of unlabeled trees (Pólya trees), with an extension of Cayley's formula
• Mixing times of a Burnside process Markov chain on set partitions
• Mixing Times for the Commuting Chain on CA Groups
• The geometry and combinatorics of Springer fibers
• Linear conditions imposed on flag varieties
• Totally positive Toeplitz matrices and quantum cohomology of partial flag varieties

Cited by

• The Dual Burnside Process

Related

• Semisimple orbits of Lie algebras and card shuffling on Coxeter groups
• Semisimple orbits of Lie algebras and card shuffling measures on Coxeter groups
• Mixing times of a Burnside process Markov chain on set partitions
• Double Coset Markov Chains
• A Markov chain on the symmetric group which is Schubert positive?