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

Abstract

Let $K\subset {\mathbb{R}}^n$ be an isotropic convex body. We prove that the hit-and-run walk, started from any $M$-warm distribution, reaches total-variation distance $\epsilon$ from the uniform distribution on $K$ in $O\left(n^2{\psi }_n^{-2}{\log }^3(M/\epsilon )\right)$ steps, where ${\psi }_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{\psi }_n^{-2}$ dependence for hit-and-run, but with polynomial dependence on $M/\epsilon$. 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.