Title: Complexity Results for MCMC derived from Quantitative Bounds,
Abstract: This paper considers how to obtain MCMC quantitative convergence bounds which
can be translated into tight complexity bounds in high-dimensional setting. We
propose a modified drift-and-minorization approach, which establishes a
generalized drift condition defined in a subset of the state space. The subset
is called the "large set", and is chosen to rule out some "bad" states which
have poor drift property when the dimension gets large. Using the "large set"
together with a "centered" drift function, a quantitative bound can be obtained
which can be translated into a tight complexity bound. As a demonstration, we
analyze a certain realistic Gibbs sampler algorithm and obtain a complexity
upper bound for the mixing time, which shows that the number of iterations
required for the Gibbs sampler to converge is constant. It is our hope that
this modified drift-and-minorization approach can be employed in many other
specific examples to obtain complexity bounds for high-dimensional Markov
chains.