Convergence Rates of the Gibbs Sampler, the Metropolis Algorithm and Other Single-Site Updating Dynamics
研究了吉布斯采样器和Metropolis算法等局部更新马尔可夫链的收敛速度，通过分析特征值比较了不同温度下Ising模型中各算法的表现，澄清了一些直观误解。
SUMMARY Sampling from a Markov random field II can be performed efficiently via Monta Carlo methods by simulating a Markov chain that converges weakly to II. We consider a class of local updating dynamics that are reversible with respect to II. It includes the Metropolis algorithm (MA) and the Gibbs sampler (GS). We investigate the speed of weak convergence of these Markov chains in terms of their second-largest eigenvalues in absolute value. We study the general algebraic structure and then the stochastic Ising model in detail. We conclude the following: the GS is faster than locally updating twice by the MA; in the Ising case, the MA is the best at low temperature but the worst at high temperature; there are dynamics faster than the GS at high temperature. The results clear up some intuitive misconceptions.