## Logarithmic Sobolev inequalities for finite Markov chains.(English)Zbl 0867.60043

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.

### MSC:

 60J27 Continuous-time Markov processes on discrete state spaces 60G50 Sums of independent random variables; random walks 60F05 Central limit and other weak theorems
Full Text:

### References:

  ALDOUS, D. and DIACONIS, P. 1987. Strong uniform times and finite random walks. Adv. in Appl. Math. 8 69 97. · Zbl 0631.60065  ALON, N. 1987. Eigenvalues and expanders. Combinatorica 5 83 96. · Zbl 0661.05053  ALON, N. and MILMAN, V. 1985., isoperimetric inequalities for graphs and superconcen1 trators. J. Combin. Theory Ser. B 38 78 88. · Zbl 0549.05051  BAKRY, D. and EMERY, M. 1985. Diffusions hy percontractive. Seminaire de Probabilite \' \' XIX. Lecture Notes in Math. 1123 179 206. Springer, Berlin.  BAKRY, D. 1994. L’hy percontractivite et son utilisation en theorie des semigroups. Ecole \' \' \' d’Ete de Saint Flour 1992. Lecture Notes in Math. 1581. Springer, Berlin. \'  BOLLOBAS, B. 1980. A probabilistic proof of an asy mptotic formula for the number of labelled regular graphs. European J. Combin. 1 311 316. · Zbl 0457.05038  DAVIES, E. B. 1989. Heat Kernels and Spectral Theory. Cambridge Univ. Press. · Zbl 0699.35006  DEUSCHEL, J-D. and STROOCK, D. 1989. Large Deviations. Academic Press, New York. · Zbl 0675.60086  DIACONIS, P. 1988. Group Representations in Probability and Statistics. IMS, Hay ward, CA. · Zbl 0695.60012  DIACONIS, P. and SALOFF-COSTE, L. 1996. Nash’s inequalities for finite Markov chains. Journal of Theoretical Probability 9 459 510. · Zbl 0870.60064  DIACONIS, P. and SALOFF-COSTE, L. 1993. Comparison techniques for random walk on finite groups. Ann. Probab. 21 2131 2156. · Zbl 0790.60011  DIACONIS, P. and SALOFF-COSTE, L. 1993. Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 696 730. · Zbl 0799.60058  DIACONIS, P. and SALOFF-COSTE, L. 1994. Moderate growth and random walk on finite groups. Geometry and Functional Analy sis 4 1 34. · Zbl 0795.60005  DIACONIS, P. and SALOFF-COSTE, L. 1995. Random walks on contingency tables with fixed row and column sums. Unpublished manuscript. · Zbl 0918.60059  DIACONIS, P. and SALOFF-COSTE, L. 1995. An application of Harnack inequalities to random walk on nilpotent quotients. Journal of Fourier Analy sis and Its Applications Z. Kahane special issue 189 207. · Zbl 0889.60008  DIACONIS, P. and SALOFF-COSTE, L. 1995. Random walks on finite groups: a survey of analytic techniques. In Probability Measures on Groups and Related Structures 11 Z. H. Hey er, ed. 46 75. World Scientific, Singapore. · Zbl 0918.60059  DIACONIS, P. and SALOFF-COSTE, L. 1996. Random walks on generating sets of finite Abelian groups. Probab. Theory Related Fields. · Zbl 0847.60081  DIACONIS, P. and SALOFF-COSTE, L. 1996. What do we know about the Metropolis algorithm J. Comput. Sy stem Sci. · Zbl 0920.68054  DIACONIS, P. and SHAHSHAHANI, M. 1981. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159 179. · Zbl 0485.60006  DIACONIS, P. and SHAHSHAHANI, M. 1987. Time to reach stationarity in the Bernoulli Laplace diffusion model. SIAM J. Math. Anal. 18 208 218. · Zbl 0617.60009  DIACONIS, P. and STROOCK, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36 61. · Zbl 0731.60061  FELLER, W. 1968. An Introduction to Probability Theory and Its Applications, 3rd ed., 1. Wiley, New York. · Zbl 0155.23101  FILL, J. 1991. Eigenvalue bounds on convergence to stationarity for nonversible Markov chains, with application to the exclusion process. Ann. Appl. Probab. 1 62 87. · Zbl 0726.60069  GROSS, L. 1976. Logarithmic Sobolev inequalities. Amer. J. Math. 97 1061 1083. JSTOR: · Zbl 0318.46049  GROSS, L. 1993. Logarithmic Sobolev inequalities and contractivity properties of semigroups. Lecture Notes in Math. 1563. Springer, Berlin. · Zbl 0812.47037  HIGUCHI, Y. and YOSHIDA, N. 1995. Analy tic conditions and phase transition for Ising Z. models. Unpublished lecture notes in Japanese.  HOLLEY, R. and STROOCK, D. 1987. Logarithmic Sobolev inequalities and stochastic Ising models. J. Statist. Phy s. 46 1159 1194. · Zbl 0682.60109  HORN, P. and JOHNSON, C. 1985. Matrix Analy sis. Cambridge Univ. Press.  HORN, P. and JOHNSON, C. 1990. Topics in Matrix Analy sis. Cambridge Univ. Press.  KORZENIOWSKI, A. and STROOCK, D. 1985. An example in the theory of hy percontractive semigroups. Proc. Amer. Math. Soc. 94 87 90. · Zbl 0577.47043  LIGGETT, T. 1985. Interacting Particle Sy stems. Springer, New York.  LU, S. L. and YAU, H. T. 1993. Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dy namics. Comm. Math. Phy s. 161 399 433. · Zbl 0779.60078  LUBOTZKY, A. 1994. Discrete Groups, Expanding Graphs and Invariant Measures. Birkhauser, Boston. \" · Zbl 0826.22012  MARGULIS, G. 1973. Explicit construction of concentrators. Problemy Peredachi Informatsii · Zbl 0312.22011  MICLO, L. 1995a. Sur les problemes de sortie discrets inhomogenes. · Zbl 0870.60062  MICLO, L. 1995b. Remarques sur l’hy percontractivite et l’evolution de l’entropie pour des \' ćhaines de Markov finies.  QUASTEL, J. 1992. Diffusion of colour in the simple exclusion process. Comm. Pure Appl. Math. 45 623 679. · Zbl 0769.60097  ROTHAUS, O. 1980. Logarithmic Sobolev inequalities and the spectrum of Sturm Liouville operators. J. Funct. Anal. 39 42 56. · Zbl 0472.47024  ROTHAUS, O. 1981. Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities. J. Funct. Anal. 42 102 109. · Zbl 0471.58027  ROTHAUS, O. 1981. Logarithmic Sobolev inequalities and the spectrum of Schrodinger öperators. J. Funct. Anal. 42 110 120. · Zbl 0471.58025  SARNACK, P. 1990. Some Applications of Modular Forms. Cambridge Univ. Press.  SINCLAIR, A. 1992. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing 1 351 370. · Zbl 0801.90039  SINCLAIR, A. 1993. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser, Boston. \" · Zbl 0780.68096  STEIN, E. 1993. Harmonic Analy sis. Princeton Univ. Press. · Zbl 0821.42001  STEIN, E. and WEISS, G. 1971. Introduction to Fourier Analy sis on Euclidean Spaces. Princeton Univ. Press. · Zbl 0232.42007  STROOCK, D. 1993. Logarithmic Sobolev inequalities for Gibbs states. Lecture Notes in Math. 1563. Springer, Berlin. · Zbl 0801.60056  STROOCK, D. and ZEGARLINSKI, B. 1992. The logarithmic Sobolev inequality for discrete spin sy stems on a lattice. Comm. Math. Phy s. 149 175 193. · Zbl 0758.60070  SU, F. 1995. Ph.D. dissertation, Harvard Univ.  YAU, T. H. 1995. Logarithmic Sobolev inequality for zero range process. Report, Dept. Mathematics, New York Univ.  CNRS, UNIVERSITE PAUL SABATIER \' HARVARD UNIVERSITY STATISTIQUE ET PROBABILITES \' DEPARTMENT OF MATHEMATICS 31062 TOULOUSE CEDEX CAMBRIDGE, MASSACHUSETTS 02138 FRANCE EMAIL: lsc.cict.fr
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.