  Adaptive Markov chains are an important class of Monte Carlo methods for
sampling from probability distributions. The time evolution of adaptive
algorithms depends on past samples, and thus these algorithms are
non-Markovian. Although there has been previous work establishing conditions
for their ergodicity, not much is known theoretically about their finite sample
properties. In this paper, using a notion of discrete Ricci curvature for
Markov kernels introduced by Ollivier, we establish concentration inequalities
and finite sample bounds for a class of adaptive Markov chains. After
establishing some general results, we give quantitative bounds for
`multi-level' adaptive algorithms such as the equi-energy sampler. We also
provide the first rigorous proofs that the finite sample properties of an
equi-energy sampler are superior to those of related parallel tempering and
Metropolis-Hastings samplers after a learning period comparable to their mixing
times.
