The chi-square mixing order of fixed-alphabet Burnside chains
We determine the order of the worst-start chi-square mixing time of the coordinate-permutation Burnside chain on words of length \(n\) over a fixed alphabet. For every fixed \(k\ge 3\), the upper bound is \(O(n/\log n)\), matching the known lower order. More generally, for the twisted chain with fixed cycle-weight parameter \(\theta>0\), chi-square distance tends to zero uniformly over all labeled starting words at time \(\lceil cn/\log n\rceil\) whenever \(c>\log k/(2\theta)\). The proof uses the established representation by products of stochastic matrices with independent Dirichlet rows. A bound on the probability that two rows have small overlap gives polynomial decay of all moments of the Dobrushin coefficient. Inserting these estimates into the trace expansion yields a stationary-average bound that decays faster than every inverse polynomial. Coordinate symmetry then gives the uniform starting-state bound.
Authors
- Sam Vaseghi (ORCID: https://orcid.org/0009-0006-4105-1949)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.5281/zenodo.24323935
- Primary Topic
- Probability and Statistical Research
- Type
- preprint