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

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

The chi-square mixing order of fixed-alphabet Burnside chains

Sam Vaseghi
1 links
Zenodo (CERN European Organization for Nuclear Research)
Probability and Statistical Research
preprint

The chi-square mixing order of fixed-alphabet Burnside chains

Sam Vaseghi
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Probability and Statistical Research
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