A new eigenvalue bound for reversible Markov chains with applications to the temperature-asymptotics of simulated annealing

摘要

A novel upper bound is presented for the second largest eigenvalue of a finite reversible time-homogeneous Markov chain as a function of three parameters, namely the smallest transition probability, the underlying structure of the chain, and the skewness of the equilibrium distribution. Simulated annealing (SA) is an example of a probabilistic algorithm that is widely used for solving combinatorial optimization problems, wherein the transition probabilities are controlled by a certain temperature parameter T<0. Using the results presented, it is possible to bound the time constant of convergence of SA to equilibrium at any fixed temperature T<0, and also to study the temperature asymptotics, namely the growth of this bound as T to 0.