Mixing time of the reflected Burnside sampler for integer partitions
Let $\mathcal{P}_n$ be the set of integer partitions of $n \ge 2$. Define a Markov kernel $Q_n$ on $\mathcal{P}_n$ by the following step from $\lambda$: take the conjugate partition $\lambda^{\mathsf{T}}$ (transpose the Young diagram); choose any $\sigma \in S_n$ of cycle type $\lambda^{\mathsf{T}}$ and sample $\tau$ uniformly from its centralizer $C_{S_n}(\sigma) = \{\tau \in S_n : \tau\sigma = \sigma\tau\}$; return the cycle type of $\tau$. The kernel does not depend on the choice of $\sigma$, and the uniform distribution on $\mathcal{P}_n$ is stationary. Let $$t_n = \min\Bigl\{t \in \mathbb{N}_0 : \max_{\lambda \in \mathcal{P}_n} \frac12 \sum_{\mu \in \mathcal{P}_n} \Bigl| Q_n^t(\lambda, \mu) - \frac{1}{|\mathcal{P}_n|} \Bigr| \le \frac14 \Bigr\}$$ be its worst-case total-variation mixing time.
This is the reflected Burnside process of Diaconis and Howes: a step of the Burnside process for $S_n$ acting on itself by conjugation, lumped to cycle types, preceded by a transposition of the Young diagram, which keeps the uniform distribution stationary since it is a bijection of $\mathcal{P}_n$. Without the transposition, the chain started at the one-part partition stays there with probability $\varphi(n)/n$, so for prime $n$ its mixing time is at least $n$. In their simulations of the reflected chain, the mixing time of every feature of the partition they considered appeared to grow logarithmically in $n$, staying below $50$ for $n$ up to $10^{10}$.
Problem. Determine the asymptotic order of $t_n$ as $n \to \infty$. In particular, is $t_n = O(\log n)$? The question concerns the law of the whole partition, uniformly over starting states.
Source: Diaconis and Howes (2025), §4.3, who observed the reflected chain's speed in simulations and ask for a quantitative explanation. Stated by AIM — Open Applied Problems as a question on the worst-case total-variation mixing time.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO, ST
- Keywords
- AIM Open Applied Problems, Burnside process, integer partitions, mixing times
References
@article{diaconis2025,
author = {Diaconis, Persi and Howes, Michael},
title = {Random sampling of contingency tables and partitions: two practical examples of the {B}urnside process},
journal = {Stat. Comput.},
volume = {35},
number = {6},
year = {2025},
pages = {181},
doi = {10.1007/s11222-025-10708-5},
eprint = {2503.02818},
archivePrefix = {arXiv},
}
@misc{aim-reflected-burnside-mixing,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Mixing time of the reflected Burnside sampler for integer partitions}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/535-reflected-burnside-mixing.md},
note = {Entry 535 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00304, "Mixing time of the reflected Burnside sampler for integer partitions", clopen.solutions.