LOGARITHMIC SOBOLEV INEQUALITIES FOR FINITE MARKOV CHAINS

• 成果类型: Article
• 署名作者: Diaconis, P.; Saloff-Coste, L.
• 署名单位: Harvard University; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1996
• 页码: 695-750
• 关键词: random-walk; diffusion; spectrum

摘要

This is an expository paper on the use of logarithmic Sobolev inequalities for bounding rates of convergence of Markov chains on finite state spaces to their stationary distributions. Logarithmic Sobolev inequalities complement eigenvalue techniques and work for nonreversible chains in continuous time. Some aspects of the theory simplify considerably with finite state spaces and we are able to give a self-contained development. Examples of applications include the study of a Metropolis chain for the binomial distribution, sharp results for natural chains on the box of side n in d dimensions and improved rates for exclusion processes. We also show that for most r-regular graphs the log-Sobolev constant is of smaller order than the spectral gap. The log-Sobolev constant of the asymmetric twopoint space is computed exactly as well as the log-Sobolev constant of the complete graph on n points.