Logarithmic Sobolev inequalities for finite Markov chains
type: Item
instance of: scholarly article
title: Logarithmic Sobolev inequalities for finite Markov chains
zbMATH Open document ID: 0867.60043
author: Persi Diaconis
author: Laurent Saloff-Coste
published in: The Annals of Applied Probability
publication date: 1997-08-04T00:00:00Z
review text: The authors describe this as an expository paper but in addition to providing an overview of its subject matter it includes many new calculations and examples. It is one of a series of papers dealing with the following question: how soon does a finite-state Markov chain reach approximate stationarity? Closeness to stationarity is measured by some distance between distributions, such as total variation, relative entropy, chi-square etc. The answer is of particular interest in the case of examples involving a dimensional or a size parameter and where one is interested in the order of magnitude of the time to approximate stationarity in terms of the parameter. In this respect logarithmic Sobolev inequalities complement traditional eigenvalue techniques and work for nonreversible chains in continuous time, although the best results are stated for reversible chains. A crucial role is played by the log-Sobolev constant which replaces the spectral gap in explicit bounds. The paper includes a reasonably self-contained treatment of logarithmic Sobolev inequalities in the context of finite Markov chains, presents the connection with hypercontractivity, compares the merits of log-Sobolev techniques with their eigenvalue counterparts and discusses a wealth of examples, often giving sharp answers to the question raised above. To cite but one example, spectral methods show that after time \(t\) of order \(n^2\) the Metropolis algorithm for the symmetric binomial distribution with parameter \(n\) is close to stationarity, while log-Sobolev methods show that order \({1\over 2} n\log n\) is sufficient. Other examples treated are natural chains on the box of side \(n\) in \(d\) dimensions, exclusion processes, random graphs, random walks on finite circles or hypercubes, random transpositions on the symmetric group etc. The paper covers continuous time as well as discrete time chains where possible and concludes with the calculation of the log-Sobolev constants of all Markov kernels o…
reviewed by: F. Papangelou
Mathematics Subject Classification ID: 60J27
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 60F05
zbMATH DE Number: 967051
zbMATH Keywords: Markov chain
zbMATH Keywords: logarithmic Sobolev inequalities
zbMATH Keywords: hypercontractivity
zbMATH Keywords: log-Sobolev techniques
zbMATH Keywords: random graphs
zbMATH Keywords: random walks
Wikidata QID: Q62111462
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1034968224
OpenAlex ID: W2077810240
cites work: Strong uniform times and finite random walks
cites work: Eigenvalues and expanders
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
cites work: Q4041031
cites work: Invariance principle and empirical mean large deviations of the critical Ornstein-Uhlenbeck process
cites work: Q3995195
cites work: Nash inequalities for finite Markov chains
cites work: Comparison techniques for random walk on finite groups
cites work: Comparison theorems for reversible Markov chains
cites work: Moderate growth and random walk on finite groups
cites work: Q4213305
cites work: An application of Harnack inequalities to random walk on nilpotent quotients
cites work: Walks on generating sets of Abelian groups
cites work: What do we know about the Metropolis algorithm?
cites work: Generating a random permutation with random transpositions
cites work: Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model
cites work: Geometric bounds for eigenvalues of Markov chains
cites work: Q5538132
cites work: Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
cites work: Logarithmic Sobolev Inequalities
cites work: Q4284289
cites work: Logarithmic Sobolev inequalities and stochastic Ising models
cites work: An Example in the Theory of Hypercontractive Semigroups
cites work: Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics
cites work: Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
cites work: Q4071451
cites work: On discrete inhomogeneous exit problems
cites work: Diffusion of color in the simple exclusion process
cites work: Logarithmic Sobolev inequalities and the spectrum of Sturm-Liouville operators
cites work: Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities
cites work: Logarithmic Sobolev inequalities and the spectrum of Schrödinger operators
cites work: Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
cites work: Q3135094
cites work: Q3142876
cites work: Q5640160
cites work: Q4284292
cites work: The logarithmic Sobolev inequality for discrete spin systems on a lattice
DOI: 10.1214/AOAP/1034968224
description: scientific article