We analyze the hit-and-run algorithm for sampling uniformly from an isotropic convex body K in n dimensions. We show that the algorithm mixes in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-total variation error with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O_\epsilon (n^2/ \psi _n^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>O</mi> <mi>ϵ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <msubsup> <mi>ψ</mi> <mi>n</mi> <mn>2</mn> </msubsup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> steps, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\psi _n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>ψ</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> is the smallest isoperimetric constant for any isotropic logconcave distribution, also known as the Kannan-Lovasz-Simonovits (KLS) constant [<CitationRef CitationID="CR19">19</CitationRef>]. Our bound improves upon previous bounds of the form <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$O_\epsilon (n^2 R^2/r^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>O</mi> <mi>ϵ</mi> </msub> <mrow> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <msup> <mi>R</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <msup> <mi>r</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, which depend on the ratio R/r of the radii of the circumscribed and inscribed balls of K, gaining a factor of n in the case of isotropic convex bodies. Consequently, our result gives a mixing time estimate for the hit-and-run which matches the state-of-the-art bounds for the ball walk. Our main proof technique is based on an annealing of localization schemes introduced in Chen and Eldan [<CitationRef CitationID="CR7">7</CitationRef>], which allows us to reduce the problem to the analysis of the mixing time on truncated Gaussian distributions.

Hit-and-Run Mixing via Localization Schemes

期刊论文
出版模式：

开放获取
发表日期：

2025年12月8日

查看全文

Yuansi Chen,
Ronen Eldan

摘要

We analyze the hit-and-run algorithm for sampling uniformly from an isotropic convex body K in n dimensions. We show that the algorithm mixes in $\epsilon $ $ϵ$ -total variation error with $O_\epsilon (n^2/ \psi _n^2)$ $O_{ϵ} (n^{2} / ψ_{n}^{2})$ steps, where $\psi _n$ $ψ_{n}$ is the smallest isoperimetric constant for any isotropic logconcave distribution, also known as the Kannan-Lovasz-Simonovits (KLS) constant [19]. Our bound improves upon previous bounds of the form $O_\epsilon (n^2 R^2/r^2)$ $O_{ϵ} (n^{2} R^{2} / r^{2})$ , which depend on the ratio R/r of the radii of the circumscribed and inscribed balls of K, gaining a factor of n in the case of isotropic convex bodies. Consequently, our result gives a mixing time estimate for the hit-and-run which matches the state-of-the-art bounds for the ball walk. Our main proof technique is based on an annealing of localization schemes introduced in Chen and Eldan [7], which allows us to reduce the problem to the analysis of the mixing time on truncated Gaussian distributions.