Mixing and Hitting Times for Gibbs Samplers and Other Non-Feller Processes

Abstract

The hitting and mixing times are two often-studied quantities associated with Markov chains. It has been previously shown that the mixing times and worst-case hitting times of reversible Markov chains on finite state spaces are equivalent - that is, equal up to some universal multiplicative constant. We have recently extended this to chains satisfying the strong Feller property. In the present paper, we further extend the results to include Metropolis-Hastings chains, the popular Gibbs sampler (from statistics) and Glauber dynamics (from statistical physics), which make one-dimensional updates and thus do not satisfy the strong Feller property. We also apply this result to obtain decomposition bounds for such Markov chains. Our main tools come from nonstandard analysis.

Date
Links