  We present a recurrence-transience classification for discrete-time Markov
chains on manifolds with negative curvature. Our classification depends only on
geometric quantities associated to the increments of the chain, defined via the
Riemannian exponential map. We deduce that there exist Markov chains on a large
class of such manifolds which are both recurrent and have zero average drift at
every point. We give an explicit example of such a chain on hyperbolic space of
arbitrary dimension, and also on a stochastically incomplete manifold. We also
prove that such recurrent chains cannot be uniformly elliptic, in contrast with
the Euclidean case.
