RAPID MIXING OF GEODESIC WALKS ON MANIFOLDS WITH POSITIVE CURVATURE

• 成果类型: Article
• 署名作者: Mangoubi, Oren; Smith, Aaron
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Ottawa
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/17-AAP1365
• 发表日期: 2018
• 页码: 2501-2543
• 关键词: algorithm; billiards

摘要

We introduce a Markov chain for sampling from the uniform distribution on a Riemannian manifold M, which we call the geodesic walk. We prove that the mixing time of this walk on any manifold with positive sectional curvature C-x(u, v) bounded both above and below by 0 < m(2) <= C-x(u, v) <= M-2 <( )infinity is O*(M-2/m(2)). In particular, this bound on the mixing time does not depend explicitly on the dimension of the manifold. In the special case that M is the boundary of a convex body, we give an explicit and computationally tractable algorithm for approximating the exact geodesic walk. As a consequence, we obtain an algorithm for sampling uniformly from the surface of a convex body that has running time bounded solely in terms of the curvature of the body.