Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing (Q2467120): Difference between revisions

A main problem in the Markov chain Monte Carlo (MCMC) methods is to find sampling schemes whose mixing times do not grow too rapidly as the size or complexity of the space is increased. In the present paper the convergence rates of Metropolis-Hastings (MH) chains to multi-modal target distributions, when the proposal distributions are of ``local chain'' and ``small worlds chains'' types are compared. The considered state space \(\Omega\) is equipped with two measures: a reference measure taken to be the Lebesgue measure \(\mu\) and a Borel probability measure \(\pi\) which serves as the target distribution. In section 1 the concepts and details of the MH algorithm, geometric ergodicity and the spectral gap which provides a measure of the speed of convergence of a Markov chain to be its stationary measure are described. \textit{J. Cheeger}'s [Probl. Analysis, Sympos. in Honor of Salomon Bochner, Princeton Univ. 1969, 195--199 (1970; Zbl 0212.44903)] inequality is reminded. The notions of log-concave, \(\alpha-\)smooth log-concave functions are given. The notions of slowly mixing and rapidly mixing in the complexity of \(\pi,\) which are given in the terms of the spectral gap, are introduced. Theorem 3.1 gives sufficient conditions that the local MH chain is slowly mixing and the small-world chain is rapidly mixing in the complexity of the multi-modal probability measure \(\pi.\) In section 2 a new version of the state decomposition theorem of \textit{N. Madras} and \textit{D. Randall} [Ann. Appl. Probab. 12, No.~2, 581--606 (2002; Zbl 1017.60080)] is proposed. Theorem 2.2 gives that the spectral gap for the whole MH chain is bounded below by taking into account the mixing speed within each mode and the mixing speed between different modes. In section 3 a lower bound on the conductance for each log-concave piece of the distribution is delivered. Theorem 3.2 is the log-concave version of the isoperimetric inequality of \textit{R. Kannan, L. Lovász} and \textit{M. Simonovits} [Discrete Comput. Geom. 13, No.~3--4, 541--559 (1995; Zbl 0824.52012)]. Theorem 3.4 states a lower bound of the conductance of the MH chain with given transition kernel induced by the uniform \(\delta\)-ball proposal. In section 4 the proof of the main result is exposed. In section 5 possible applications of the obtained results to convergence rates in Metropolis-coupled MCMC are discussed.