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\ge3$, 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.
From: Ivan Feng [view email]
[v1]
Wed, 29 Oct 2025 06:14:29 UTC (165 KB)
[v2]
Mon, 17 Nov 2025 17:50:20 UTC (269 KB)
[v3]
Wed, 20 May 2026 17:49:28 UTC (245 KB)
[v4]
Sun, 30 Aug 2026 21:30:54 UTC (39 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。