On the mixing time of coordinate Hit-and-Run
Combinatorics, Probability and Computing · 2022-03 · 31 (2) · 320-332
DOI: 10.1017/s0963548321000328 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorics, Probability and Computing, online erschienen am 25.08.2021. Verfasst von Hariharan Narayanan und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 21 Literaturangaben.
Abstract (Originalsprache)
We obtain a polynomial upper bound on the mixing time $T_{CHR}(\epsilon)$ of the coordinate Hit-and-Run (CHR) random walk on an $n-$ dimensional convex body, where $T_{CHR}(\epsilon)$ is the number of steps needed to reach within $\epsilon$ 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}{\epsilon}$ , 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 CHR has a polynomial mixing time has been an open question.
Zitieren
APA
Narayanan, H., & Srivastava, P. (2022). On the mixing time of coordinate Hit-and-Run. Combinatorics, Probability and Computing, 31(2), 320-332. https://doi.org/10.1017/s0963548321000328
Vancouver
Narayanan H, Srivastava P. On the mixing time of coordinate Hit-and-Run. Combinatorics, Probability and Computing. 2022;31(2):320-332. doi:10.1017/s0963548321000328
BibTeX
@article{Narayanan2022,
author = {Narayanan, Hariharan and Srivastava, Piyush},
title = {On the mixing time of coordinate Hit-and-Run},
journal = {Combinatorics, Probability and Computing},
year = {2022},
volume = {31},
number = {2},
pages = {320--332},
doi = {10.1017/s0963548321000328}
}
EUVIMED