  The multiple-try Metropolis (MTM) algorithm is an extension of the
Metropolis-Hastings (MH) algorithm by selecting the proposed state among
multiple trials according to some weight function. Although MTM has gained
great popularity owing to its faster empirical convergence and mixing than the
standard MH algorithm, its theoretical mixing property is rarely studied in the
literature due to its complex proposal scheme. We prove that MTM can achieve a
mixing time bound smaller than that of MH by a factor of the number of trials
under a general setting applicable to high-dimensional model selection problems
with discrete state spaces. Our theoretical results motivate a new class of
weight functions called locally balanced weight functions and guide the choice
of the number of trials, which leads to improved performance over standard MTM
algorithms. We support our theoretical results by extensive simulation studies
and real data applications with several Bayesian model selection problems.
