Quadratic mixing for the Lee--Sidford Dikin walk
Abstract
Let K={x∈Rd:Ax≥ b} be a bounded full-dimensional polytope with m inequalities. For targets on K with density proportional to exp(−ϑtranspose x), we prove a Õ(d2) bound, measured in Markov chain iterations, for the chi-square mixing of the 1/2-lazy Metropolis Dikin walk based on a polylogarithmically rescaled Lee--Sidford metric. The estimate holds for every initial law with finite chi-square divergence. The proof controls the reverse Gaussian proposal through a quantitative average self-concordance estimate at the required O(1/d) scale. We establish this estimate from uniform analytic derivative bounds for the Lewis-weight subspace and an all-order projection-weighted contraction inequality for Gaussian chaoses. For order j, the latter bounds each base-point polynomial at scale dj/2, up to j-dependent and logarithmic factors. Truncating at logarithmic order then absorbs the remaining pathwise loss. This resolves, in the affirmative, the open problem of whether the Gaussian Lee--Sidford Dikin walk mixes in Õ(d2) iterations: the previously stated quadratic bounds \cite[Theorem~1.4]{LLV20}, \cite[Theorem~1.2]{GKM24} rest on reverse-proposal steps identified as unresolved in \cite[Section~1]{Kook26}, whose Õ(d9/4) bound was the best rigorously established rate prior to this work. The proof is found by ChatGPT 5.6 Pro.
Related
- Resolvent characteristics and quadratic mixing of Kac's walk on SO(n)
- On two proofs of d2 mixing of weighted Dikin walks
- Mixing time of the lazy and simple random walk on a randomly twisted hypercube
- Mixing time of the tranvection walk on SLn(ℤp)
- From Ehrenfest to Heisenberg scales: a hierarchy of mixing times for a phase-randomized quantum baker walk
BibTeX
@misc{lu2026quadratic,
title = {{Quadratic mixing for the Lee--Sidford Dikin walk}},
author = {Yiping Lu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22374},
eprint = {2610.22374},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22374},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quadratic mixing for the Lee--Sidford Dikin walk
AU - Yiping Lu
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.22374
UR - https://arxiv.org/abs/2610.22374
AB - Let K={x∈R^d:Ax≥ b} be a bounded full-dimensional polytope with m inequalities. For targets on K with density proportional to exp(−ϑ^transpose x), we prove a Õ(d^2) bound, measured in Markov chain iterations, for the chi-square mixing of the 1/2-lazy Metropolis Dikin walk based on a polylogarithmically rescaled Lee--Sidford metric. The estimate holds for every initial law with finite chi-square divergence. The proof controls the reverse Gaussian proposal through a quantitative average self-concordance estimate at the required O(1/d) scale. We establish this estimate from uniform analytic derivative bounds for the Lewis-weight subspace and an all-order projection-weighted contraction inequality for Gaussian chaoses. For order j, the latter bounds each base-point polynomial at scale d^j/2, up to j-dependent and logarithmic factors. Truncating at logarithmic order then absorbs the remaining pathwise loss. This resolves, in the affirmative, the open problem of whether the Gaussian Lee--Sidford Dikin walk mixes in Õ(d^2) iterations: the previously stated quadratic bounds \cite[Theorem~1.4]{LLV20}, \cite[Theorem~1.2]{GKM24} rest on reverse-proposal steps identified as unresolved in \cite[Section~1]{Kook26}, whose Õ(d^9/4) bound was the best rigorously established rate prior to this work. The proof is found by ChatGPT 5.6 Pro.
ER -