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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A mixing lower bound for the Pólya-tree Burnside sampler

Sam Vaseghi
Zenodo (CERN European Organization for Nuclear Research)
Markov Chains and Monte Carlo Methods
preprint

A mixing lower bound for the Pólya-tree Burnside sampler

Sam Vaseghi
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Markov Chains and Monte Carlo Methods
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon