
























We obtain a polynomial upper bound on the mixing time $T_{CHR}(ε)$ of the coordinate Hit-and-Run random walk on an $n-$dimensional convex body, where $T_{CHR}(ε)$ is the number of steps needed in order to reach within $ε$ of the uniform distribution with respect to the total variation distance, starting from a warm start (i.e., a distribution which has a density with respect to the uniform distribution on the convex body that is bounded above by a constant). Our upper bound is polynomial in $n, R$ and $\frac{1}ε$, where we assume that the convex body contains the unit $\Vert\cdot\Vert_\infty$-unit ball $B_\infty$ and is contained in its $R$-dilation $R\cdot B_\infty$. Whether coordinate Hit-and-Run has a polynomial mixing time has been an open question.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。