The dual Burnside process

Abstract

The Burnside process is a classical Markov chain for sampling uniformly from group orbits. We give a systematic study of the dual Burnside process, obtained by interchanging the roles of group elements and states. This dual chain has stationary law $\pi (g)\propto |X_g|$, is reversible, and admits a matrix factorization $Q=AB$, $K=BA$ with the classical Burnside kernel $K$. As a consequence, the two chains share all nonzero eigenvalues and have mixing times that differ by at most one step. We further establish universal Doeblin floors, orbit- and conjugacy-class lumpings, exact stabilizer/fixed-set quotient pairs, and transfer principles between $Q$ and $K$. We analyze the explicit examples of the value-permutation model $S_k$ acting on $[k{]}^n$ and the coordinate-permutation model $S_n$ acting on $[k{]}^n$. In the value-permutation model, for fixed $k\ge 3$, the dual fixed-symbol-set quotient has $2^k-k-1$ states, independent of $n$, preserves the full nonzero spectrum, and has limiting nontrivial spectral radius $1/2$. These results show that the dual chain provides both a conceptual mirror to the classical Burnside process and a genuinely useful compression mechanism for symmetry-aware Markov chain Monte Carlo.

arXiv comment49 pages, 2 figures. Text updated to agree with the published article

References in corpus (1)

• Random sampling of contingency tables and partitions: Two practical examples of the Burnside process