Logarithmic Sobolev inequalities for finite Markov chains (Q2564686): Difference between revisions

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 on a two-point space and of sequences of i.i.d. random elements from a finite state space.