pith. sign in

arxiv: 2510.25202 · v3 · pith:DDCEZLPKnew · submitted 2025-10-29 · 🧮 math.PR · math.CO· math.GR

The dual Burnside process

Ivan Z. Feng This is my paper

Pith reviewed 2026-05-22 12:16 UTC · model grok-4.3

classification 🧮 math.PR math.COmath.GR
keywords dual Burnside processMarkov chaingroup orbitsmatrix factorizationmixing timeMCMCreversible chainquotient chain
0
0 comments X

The pith

The dual Burnside process obtained by swapping group elements and states shares all nonzero eigenvalues with the classical kernel and mixes in at most one extra step.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the dual Burnside process by interchanging the roles of group elements and states in the classical Burnside chain for sampling from group orbits. The resulting chain is reversible with stationary distribution proportional to fixed-set sizes and satisfies a matrix factorization Q equals A B and K equals B A with the original Burnside kernel K. This factorization immediately implies that the two chains share every nonzero eigenvalue and that their mixing times differ by at most one step. The author further derives universal Doeblin floors, orbit and conjugacy-class lumpings, exact stabilizer and fixed-set quotient pairs, and transfer principles that move information between the two kernels. In concrete models such as the value-permutation action of S_k on [k]^n the dual admits a fixed-symbol-set quotient with only 2^k minus k minus 1 states independent of n that preserves the full nonzero spectrum and has limiting nontrivial spectral radius one half.

Core claim

By interchanging the roles of group elements and states one obtains a dual reversible Markov chain Q whose transition probabilities are the normalized fixed-set sizes; this chain satisfies Q equals A B and K equals B A for the classical Burnside kernel K, hence the two chains share all nonzero eigenvalues and their mixing times differ by at most one step.

What carries the argument

The matrix factorization Q=AB, K=BA that links the dual transition matrix to the classical Burnside kernel.

If this is right

  • The dual and classical chains share the entire nonzero spectrum.
  • Mixing times of the two chains differ by at most one step.
  • Orbit and conjugacy-class lumpings exist for the dual chain.
  • Exact stabilizer and fixed-set quotient pairs relate the two processes.
  • Transfer principles allow spectral information to move between Q and K.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The fixed-size quotient in the value-permutation model suggests that symmetry compression can be performed before running any chain and may extend to other group actions with large n.
  • The one-step mixing difference raises the possibility that the dual could serve as a preprocessing accelerator for classical Burnside sampling.
  • The same role-swapping construction might produce duals for other orbit-sampling chains on different algebraic structures.
  • Doeblin floors and transfer principles could be used to bound convergence rates uniformly across families of groups.

Load-bearing premise

Interchanging the roles of group elements and states produces a well-defined reversible Markov chain whose transition probabilities are given by the normalized fixed-set sizes.

What would settle it

Compute the transition matrix of the dual chain and the classical kernel for S_3 acting on [3]^2 and check whether every nonzero eigenvalue of one appears in the other; mismatch would refute the claimed factorization.

Figures

Figures reproduced from arXiv: 2510.25202 by Ivan Z. Feng.

Figure 1
Figure 1. Figure 1: Primal–dual alternation via the legs A and B. Finally, this picture intuitively illustrates the relationship between the primal and dual chains developed in this section. It shows the alternating–leg walk on E = G∗ ⊔ X: black A-arrows are G→X steps and black B-arrows are X →G steps, so the two legs in X give K = BA (blue arrows) and two legs in G∗ give Q = AB (red arrows). This yields the one–step TV lag d… view at source ↗
Figure 2
Figure 2. Figure 2: Orbits of ⟨h⟩ and color counts Ma(ϕ). Start from the colorings form (36): Q(e, h) = 1 k n X ϕ:[s]→[k] Y k a=1 1 Ma(ϕ)! [PITH_FULL_IMAGE:figures/full_fig_p051_2.png] view at source ↗
read the original abstract

The Burnside process is a classical Markov chain for sampling uniformly from group orbits. We introduce 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces the dual Burnside process obtained by interchanging the roles of group elements and states in the classical Burnside Markov chain for sampling uniformly from group orbits. It establishes that the dual chain is reversible with stationary distribution π(g) ∝ |X_g|, admits the matrix factorization Q = AB and K = BA with the classical Burnside kernel K (implying shared nonzero eigenvalues and mixing times differing by at most one step), and proves universal Doeblin floors, orbit- and conjugacy-class lumpings, exact stabilizer/fixed-set quotient pairs, and transfer principles between Q and K. Explicit analysis is given for the value-permutation model S_k acting on [k]^n (yielding a dual fixed-symbol-set quotient with 2^k - k - 1 states independent of n that preserves the nonzero spectrum and has limiting nontrivial spectral radius 1/2) and the coordinate-permutation model S_n acting on [k]^n.

Significance. If the results hold, the work supplies both a conceptual mirror to the classical Burnside process and a practical compression mechanism for symmetry-aware MCMC via spectral-preserving quotients whose size is independent of n. The matrix factorization Q = AB, K = BA is a standard linear-algebra device, but its application here yields concrete mixing-time bounds, lumpings, and transfer principles that strengthen the contribution. The paper supplies explicit examples and parameter-free quotient constructions, which are strengths for applicability and verification in the field.

minor comments (2)
  1. [§3] The definition of the incidence matrices A and B in the factorization Q = AB, K = BA would benefit from an explicit display of their entries (normalized fixed-set sizes) immediately before the statement of the eigenvalue-sharing result.
  2. [§5.1] In the value-permutation model analysis, the explicit 2^k - k - 1 state count for the dual fixed-symbol-set quotient is stated clearly, but a short table listing the states for small k (e.g., k = 3) would improve readability without altering the argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work, the assessment of its significance, and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

Derivation is self-contained with no circularity

full rationale

The dual Burnside process is introduced by explicitly interchanging the roles of group elements and states, with transitions defined via normalized fixed-set sizes. Reversibility with respect to π(g) ∝ |X_g| follows immediately from the symmetry of the joint fixed-point count. The factorization Q = AB and K = BA is obtained by taking A and B to be the normalized incidence matrices between G and X; this equality holds by direct construction of the transition probabilities rather than by any independent derivation. The shared nonzero eigenvalues and the mixing-time relation differing by at most one step are then immediate consequences of the general linear-algebra fact that AB and BA share the same nonzero spectrum. No self-citations are invoked as load-bearing premises, no parameters are fitted to data, and no ansatz is imported from prior work. The entire chain is therefore self-contained and does not reduce any claimed result to its own inputs by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on the standard definition of the Burnside kernel together with the new role-interchange construction; no free parameters are fitted and no new entities are postulated beyond the dual chain itself.

axioms (1)
  • domain assumption Interchanging the roles of group elements and states produces a valid transition kernel on the group with stationary law proportional to fixed-set cardinalities.
    This is the foundational definition of the dual process invoked throughout the abstract.

pith-pipeline@v0.9.0 · 5752 in / 1329 out tokens · 51335 ms · 2026-05-22T12:16:56.639653+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Burnside process on parking functions and Dyck paths

    math.PR 2026-05 unverdicted novelty 7.0

    Burnside processes on parking functions and Dyck paths mix in O(n log n) time, yielding approximate uniform sampling algorithms for increasing parking functions, Dyck paths, and polygon triangulations.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Aldous and J

    D. Aldous and J. Fill,Reversible Markov Chains and Random Walks on Graphs, monograph in progress (2002). https://www.stat.berkeley.edu/~aldous/RWG/book.pdf

    work page 2002

  2. [2]

    Athanasiadis and P

    C. Athanasiadis and P. Diaconis,Functions of Random Walks on Hyperplane Arrangements, Adv. Appl. Math. 45(2010), no. 3, 410–437

    work page 2010

  3. [3]

    Bartholdi and P

    L. Bartholdi and P. Diaconis,An algorithm for uniform generation of unlabeled trees (P´ olya trees), with an extension of Cayley’s formula, arXiv:2411.17613 (2024)

    work page arXiv 2024

  4. [4]

    Br´ emaud,Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues, Springer, 1999

    P. Br´ emaud,Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues, Springer, 1999

    work page 1999

  5. [5]

    Burnside,Theory of Groups of Finite Order, Cambridge Univ

    W. Burnside,Theory of Groups of Finite Order, Cambridge Univ. Press, 1897

    work page

  6. [6]

    Chatterjee and P

    S. Chatterjee and P. Diaconis, A central limit theorem for a new statistic on permutations,Indian J. Pure Appl. Math.48 (2017), 561–573

    work page 2017

  7. [7]

    Chen,Mixing Times for Burnside Processes, M.Sc

    W.-K. Chen,Mixing Times for Burnside Processes, M.Sc. Thesis, National Chiao Tung University, Hsinchu, Taiwan, July 2006

    work page 2006

  8. [8]

    N. G. de Bruijn,Asymptotic Methods in Analysis, Dover, 1981

    work page 1981

  9. [9]

    Diaconis,Group Representations in Probability and Statistics, IMS Lecture Notes—Monograph 11, 1988

    P. Diaconis,Group Representations in Probability and Statistics, IMS Lecture Notes—Monograph 11, 1988

    work page 1988

  10. [10]

    Diaconis, Analysis of a Bose–Einstein Markov chain,Ann

    P. Diaconis, Analysis of a Bose–Einstein Markov chain,Ann. Inst. H. Poincar´ e Probab. Statist.41 (2005), 409–418

    work page 2005

  11. [11]

    Diaconis and J

    P. Diaconis and J. Fill, Strong stationary times via a new form of duality,Ann. Probab.18 (1990), 1483–1522

    work page 1990

  12. [12]

    Diaconis and M

    P. Diaconis and M. Howes, Random sampling of partitions and contingency tables: two practical examples of the Burnside process,Stat. Comput.(2025), arXiv:2503.02818

    work page arXiv 2025

  13. [13]

    Diaconis, K

    P. Diaconis, K. Khare, and L. Saloff–Coste,Gibbs sampling, exponential families and orthogonal polynomials, Ann. Appl. Probab.18(2008), no. 4, 1586–1619

    work page 2008

  14. [14]

    Diaconis, A

    P. Diaconis, A. Lin, and A. Ram,A curiously slowly mixing Markov chain, arXiv:2511.01245 (2025)

    work page arXiv 2025

  15. [15]

    Diaconis and C

    P. Diaconis and C. Morton–Ferguson,The Burnside process on the flag variety forGL n(Fq), arXiv:2510.02285 (2025)

    work page arXiv 2025

  16. [16]

    Diaconis and D

    P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains,Ann. Appl. Probab.1 (1991), 36–61

    work page 1991

  17. [17]

    Diaconis and C

    P. Diaconis and C. Zhong, Hahn polynomials and the Burnside process,J. Algebraic Combin.59 (2024), 115–142

    work page 2024

  18. [18]

    Diaconis and C

    P. Diaconis and C. Zhong, Counting the number of group orbits by marrying the Burnside process with impor- tance sampling, arXiv:2501.11731 [math.PR], 2025

    work page arXiv 2025

  19. [19]

    Dittmer,Counting and Sampling Double Cosets and Applications, Ph.D

    J. Dittmer,Counting and Sampling Double Cosets and Applications, Ph.D. thesis, University of California, Los Angeles, 2023.https://www.math.ucla.edu/ ~pak/papers/Dittmer-thesis.pdf

    work page 2023

  20. [20]

    Feller,An Introduction to Probability Theory and Its Applications, Vol

    W. Feller,An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed., Wiley, 1968

    work page 1968

  21. [21]

    Flajolet and R

    P. Flajolet and R. Sedgewick,Analytic Combinatorics, Cambridge Univ. Press, 2009

    work page 2009

  22. [22]

    Fulman, Cycle indices for the finite classical groups,J

    J. Fulman, Cycle indices for the finite classical groups,J. Group Theory2(1999), 251–289

    work page 1999

  23. [23]

    L. A. Goldberg and M. Jerrum, The Burnside process converges slowly,Combin. Probab. Comput.11 (2002), 21–34

    work page 2002

  24. [24]

    Gr¨ unwald and S

    L. Gr¨ unwald and S. Serafin, Explicit bounds for Bell numbers and their ratios,J. Math. Anal. Appl.540 (2024), 128651

    work page 2024

  25. [25]

    Holtzen, T

    S. Holtzen, T. Millstein and G. Van den Broeck, Generating and sampling orbits for lifted probabilistic inference, inProc. UAI 2020, PMLR 115 (2020), 985–994

    work page 2020

  26. [26]

    R. A. Horn and C. R. Johnson,Matrix Analysis, 2nd ed., Cambridge University Press, 2013

    work page 2013

  27. [27]

    Howes,Limit profiles and cutoff for the Burnside process on Sylow double cosets, arXiv:2511.01058 (2025)

    M. Howes,Limit profiles and cutoff for the Burnside process on Sylow double cosets, arXiv:2511.01058 (2025)

    work page arXiv 2025

  28. [28]

    Jerrum, Uniform sampling modulo a group of symmetries using Markov-chain simulation, inExpanding Graphs, DIMACS 10, AMS, 1993, 37–47

    M. Jerrum, Uniform sampling modulo a group of symmetries using Markov-chain simulation, inExpanding Graphs, DIMACS 10, AMS, 1993, 37–47

    work page 1993

  29. [29]

    Koekoek and R

    R. Koekoek and R. F. Swarttouw,The Askey Scheme of Hypergeometric Orthogonal Polynomials and itsq- Analogue, Tech. Report 98-17, Delft Univ., 1998

    work page 1998

  30. [30]

    D. A. Levin and Y. Peres,Markov Chains and Mixing Times, 2nd ed., Amer. Math. Soc., 2017

    work page 2017

  31. [31]

    The low-rank eigenvalue problem

    Y. Nakatsukasa, The low-rank eigenvalue problem, arXiv:1905.11490, 2019

    work page internal anchor Pith review Pith/arXiv arXiv 1905

  32. [32]

    J. E. Paguyo, Mixing times of a Burnside process Markov chain on set partitions, arXiv:2207.14269 [math.PR], 2022

    work page arXiv 2022

  33. [33]

    Rahmani,Mixing Times for the Commuting Chain, Ph.D

    J. Rahmani,Mixing Times for the Commuting Chain, Ph.D. thesis, University of Southern California, 2021. THE DUAL BURNSIDE PROCESS 63

    work page 2021

  34. [34]

    Rahmani, Mixing times for the commuting chain on CA groups,J

    J. Rahmani, Mixing times for the commuting chain on CA groups,J. Theor. Probab.35 (2022), 1382–1409

    work page 2022

  35. [35]

    Riordan,An Introduction to Combinatorial Analysis, Wiley, 1958

    J. Riordan,An Introduction to Combinatorial Analysis, Wiley, 1958

    work page 1958

  36. [36]

    J. S. Rosenthal, Minorization conditions and convergence rates for Markov chain Monte Carlo,Journal of the American Statistical Association90(1995), no. 430, 558–566

    work page 1995

  37. [37]

    B. E. Sagan,The Symmetric Group, 2nd ed., Grad. Texts in Math. 203, Springer, 2001

    work page 2001

  38. [38]

    Sinclair and M

    A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains,Inf. Comput.82 (1989), 93–133

    work page 1989

  39. [39]

    Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow,Combin

    A. Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow,Combin. Probab. Comput.1 (1992), 351–370

    work page 1992

  40. [40]

    R. P. Stanley,Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge Univ. Press, 2012. Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532, USA Email address:ifeng@usc.edu URL:https://dornsife.usc.edu/ivan/

    work page 2012