Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 43 min ago
PreprintCC BY 4.0arXiv

Hit-and-Run Mixes as Fast as the Ball Walk

  • Ruizhe Zhang
Open at sourcePDFDOICite

Abstract

Let K⊂ℝn be an isotropic convex body. We prove that the hit-and-run walk, started from any M-warm distribution, reaches total-variation distance ε from the uniform distribution on K in O (n2ψn−2log3(M/ε)) steps, where ψn−1 is the Kannan-Lovász-Simonovits (KLS) constant. Up to logarithmic factors, this matches the best-known warm-start mixing time for the ball walk. Chen and Eldan [Discrete Comput. Geom. 2026] obtained the same n2ψn−2 dependence for hit-and-run, but with polynomial dependence on M/ε. Our result improves that polynomial dependence to a polylogarithmic one, fully resolving their open question about warm-start mixing of hit-and-run in isotropic convex bodies.

Related

  1. Kac's Walk on Rotation Matrices Mixes in Θ(n2) Steps: A Proof Discovered with AI
    Tianle Liu
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  2. Renormalizing small ball events for branching random walk
    Vilas Winstein
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv
  3. Fast Rates and Strong Convergence of Tikhonov-Regularized Mixed-Order Primal-Dual Dynamics for Linearly Constrained Optimization Without Eventual Ball Conditions
    Hong-lu Li, Yi-bin Xiao
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  4. The Aldous chain on cladograms mixes in order n2 steps
    Valentin Féray, Lucas Teyssier
    HALPreprintCC0Full textCombinatorics & discrete mathematicsProbabilityHALarXiv
  5. On the critical branching random walk I: branching capacity and visiting probability
    Qingsan Zhu
    Probability Theory and Related FieldsPeer-reviewedLicence not statedFull text21 citedMathematical physicsOpenAlex

Cite

BibTeXRIS
BibTeX
@misc{zhang2026hitandrun,
  title = {{Hit-and-Run Mixes as Fast as the Ball Walk}},
  author = {Ruizhe Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.13487},
  eprint = {2608.13487},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.13487},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Hit-and-Run Mixes as Fast as the Ball Walk
AU  - Ruizhe Zhang
PY  - 2026
DA  - 2026/09/05
PB  - arXiv
DO  - 10.48550/arxiv.2608.13487
UR  - https://arxiv.org/abs/2608.13487
AB  - Let K⊂ℝ^n be an isotropic convex body. We prove that the hit-and-run walk, started from any M-warm distribution, reaches total-variation distance ε from the uniform distribution on K in O (n^2ψ_n^−2log^3(M/ε)) steps, where ψ_n^−1 is the Kannan-Lovász-Simonovits (KLS) constant. Up to logarithmic factors, this matches the best-known warm-start mixing time for the ball walk. Chen and Eldan [Discrete Comput. Geom. 2026] obtained the same n^2ψ_n^−2 dependence for hit-and-run, but with polynomial dependence on M/ε. Our result improves that polynomial dependence to a polylogarithmic one, fully resolving their open question about warm-start mixing of hit-and-run in isotropic convex bodies.
ER  -