Rapid Mixing of Geodesic Walks on Manifolds with Positive Curvature

We introduce a Markov chain for sampling from the uniform distribution on a Riemannian manifold $\mathcal{M}$, which we call the $\mathit{\text{geodesic}}\mathit{\text{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 < \mathfrak{m}{2} \leq C{x}(u,v) \leq \mathfrak{M}_2 < \infty$is$$\mathcal{O}$^*\left(\frac{\mathfrak{M}_2}{\mathfrak{m}_2}\right)$. In particular, this bound on the mixing time does not depend explicitly on the dimension of the manifold. In the special case that $\mathcal{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.