A mixing lower bound for the Pólya-tree Burnside sampler
Bartholdi and Diaconis observed that several statistics of their sampler for uniform unlabeled rooted trees appeared to stabilize after about twenty sweeps from a star. We prove that the tree retains a trace of this initial symmetry in large families of identical branches. For every fixed \(0<c<\sqrt{8/\pi}\), after \(\lfloor c\sqrt{\log n}\rfloor\) sweeps from the centered star on \(n\) vertices, the total variation distance from the uniform law tends to one as \(n\) grows. Even the expected width after any fixed number of sweeps exceeds its stationary mean by a factor tending to infinity. The proof uses large prime divisors of random permutation orders to carry a lower bound on branch multiplicity from one tree to the next.
Authors
- Sam Vaseghi (ORCID: https://orcid.org/0009-0006-4105-1949)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24339319
- Primary Topic
- Markov Chains and Monte Carlo Methods
- Type
- preprint