论文标题
在坐标的混合时间上
On the mixing time of coordinate Hit-and-Run
论文作者
论文摘要
我们在混合时间上获得了一个多项式上限，$ t_ {chr}（ε）$在$ n- $ dimensional convex主体上随机步行，其中$ t_ {chr}（chr}（ε）$是为了在$ε$中与均匀分布的均匀分布的$ε$到达的分布（i。在凸体上，以上方的限制）。我们的上限在$ n，r $和$ \ frac {1}ε$中是多项式的，在那里我们假设凸面包含$ \ vert \ cdot \ cdot \ cdot \ vert_ \ vert_ \ infty $ undty $ unit $ unit ball $ b_ \ infty $，并且包含在其$ r $ r $ r $ r $ r \ cdot $ r \ cdot b_ \ cdot b_ \ suftty $中。坐标是否具有多项式混合时间是一个悬而未决的问题。
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.
