Abstract
Convergence analysis of Markov chain Monte Carlo methods in high-dimensionalstatistical applications is increasingly recognized. In this paper, we developgeneral mixing time bounds for Metropolis-Hastings algorithms on discretespaces by building upon and refining some recent theoretical advancements inBayesian model selection problems. We establish sufficient conditions for aclass of informed Metropolis-Hastings algorithms to attain relaxation timesthat are independent of the problem dimension. These conditions are grounded inthe high-dimensional statistical theory and allow for possibly multimodalposterior distributions. We obtain our results through two independenttechniques: the multicommodity flow method and single-element drift conditionanalysis; we find that the latter yields a slightly tighter mixing time bound.Our results are readily applicable to a broad spectrum of statistical problemswith discrete parameter spaces, as we demonstrate using both theoretical andnumerical examples.