  We introduce a Markov chain for sampling from the uniform distribution on a
Riemannian manifold $\mathcal{M}$, which we call the $\textit{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 <
\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.
