On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds. (English) Zbl 0802.60061

Ingrassia, Salvatore

Ann. Appl. Probab. 4, No. 2, 347-389 (1994).

Summary: We obtain bounds on the spectral gap of the transition probability matrix of Markov chains associated with the Metropolis algorithm and with the Gibbs sampler. In both cases we prove that, for small values of \(T\), the spectral gap is equal to \(1-\lambda_ 2\), where \(\lambda_ 2\) is the second largest eigenvalue of \(P\). In the case of the Metropolis algorithm we give also two examples in which the spectral gap is equal to \(1- \lambda_{\min}\), where \(\lambda_{\min}\) is the smallest eigenvalue of \(P\). Furthermore we prove that random updating dynamics on sites based on the Metropolis algorithm and on the Gibbs sampler have the same rate of convergence at low temperatures. The obtained bounds are discussed and compared with those obtained with a different approach.

MSC:

60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
60G50	Sums of independent random variables; random walks
15A42	Inequalities involving eigenvalues and eigenvectors

Keywords:

bounds; spectral gap; transition probability matrix; Metropolis algorithm; Gibbs sampler; random updating dynamics; rate of convergence at low temperatures