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

Diaconis, P.; Saloff-Coste, L.

Ann. Appl. Probab. 6, No. 3, 695-750 (1996).

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.

Reviewer: F.Papangelou (Manchester)

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

Keywords:

Markov chain; logarithmic Sobolev inequalities; hypercontractivity; log-Sobolev techniques; random graphs; random walks

References:

[1]	ALDOUS, D. and DIACONIS, P. 1987. Strong uniform times and finite random walks. Adv. in Appl. Math. 8 69 97. · Zbl 0631.60065 · doi:10.1016/0196-8858(87)90006-6
[2]	ALON, N. 1987. Eigenvalues and expanders. Combinatorica 5 83 96. · Zbl 0661.05053 · doi:10.1007/BF02579166
[3]	ALON, N. and MILMAN, V. 1985., isoperimetric inequalities for graphs and superconcen1 trators. J. Combin. Theory Ser. B 38 78 88. · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9
[4]	BAKRY, D. and EMERY, M. 1985. Diffusions hy percontractive. Seminaire de Probabilite \' \' XIX. Lecture Notes in Math. 1123 179 206. Springer, Berlin.
[5]	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. \'
[6]	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 · doi:10.1016/S0195-6698(80)80030-8
[7]	DAVIES, E. B. 1989. Heat Kernels and Spectral Theory. Cambridge Univ. Press. · Zbl 0699.35006
[8]	DEUSCHEL, J-D. and STROOCK, D. 1989. Large Deviations. Academic Press, New York. · Zbl 0675.60086 · doi:10.1214/aop/1176991495
[9]	DIACONIS, P. 1988. Group Representations in Probability and Statistics. IMS, Hay ward, CA. · Zbl 0695.60012
[10]	DIACONIS, P. and SALOFF-COSTE, L. 1996. Nash’s inequalities for finite Markov chains. Journal of Theoretical Probability 9 459 510. · Zbl 0870.60064 · doi:10.1007/BF02214660
[11]	DIACONIS, P. and SALOFF-COSTE, L. 1993. Comparison techniques for random walk on finite groups. Ann. Probab. 21 2131 2156. · Zbl 0790.60011 · doi:10.1214/aop/1176989013
[12]	DIACONIS, P. and SALOFF-COSTE, L. 1993. Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 696 730. · Zbl 0799.60058 · doi:10.1214/aoap/1177005359
[13]	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 · doi:10.1007/BF01898359
[14]	DIACONIS, P. and SALOFF-COSTE, L. 1995. Random walks on contingency tables with fixed row and column sums. Unpublished manuscript. · Zbl 0918.60059
[15]	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
[16]	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
[17]	DIACONIS, P. and SALOFF-COSTE, L. 1996. Random walks on generating sets of finite Abelian groups. Probab. Theory Related Fields. · Zbl 0847.60081 · doi:10.1007/BF01192214
[18]	DIACONIS, P. and SALOFF-COSTE, L. 1996. What do we know about the Metropolis algorithm J. Comput. Sy stem Sci. · Zbl 0920.68054 · doi:10.1006/jcss.1998.1576
[19]	DIACONIS, P. and SHAHSHAHANI, M. 1981. Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159 179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[20]	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 · doi:10.1137/0518016
[21]	DIACONIS, P. and STROOCK, D. 1991. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36 61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980
[22]	FELLER, W. 1968. An Introduction to Probability Theory and Its Applications, 3rd ed., 1. Wiley, New York. · Zbl 0155.23101
[23]	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 · doi:10.1214/aoap/1177005981
[24]	GROSS, L. 1976. Logarithmic Sobolev inequalities. Amer. J. Math. 97 1061 1083. JSTOR: · Zbl 0318.46049 · doi:10.2307/2373688
[25]	GROSS, L. 1993. Logarithmic Sobolev inequalities and contractivity properties of semigroups. Lecture Notes in Math. 1563. Springer, Berlin. · Zbl 0812.47037 · doi:10.1007/BFb0074091
[26]	HIGUCHI, Y. and YOSHIDA, N. 1995. Analy tic conditions and phase transition for Ising Z. models. Unpublished lecture notes in Japanese.
[27]	HOLLEY, R. and STROOCK, D. 1987. Logarithmic Sobolev inequalities and stochastic Ising models. J. Statist. Phy s. 46 1159 1194. · Zbl 0682.60109 · doi:10.1007/BF01011161
[28]	HORN, P. and JOHNSON, C. 1985. Matrix Analy sis. Cambridge Univ. Press.
[29]	HORN, P. and JOHNSON, C. 1990. Topics in Matrix Analy sis. Cambridge Univ. Press.
[30]	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 · doi:10.2307/2044957
[31]	LIGGETT, T. 1985. Interacting Particle Sy stems. Springer, New York.
[32]	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 · doi:10.1007/BF02098489
[33]	LUBOTZKY, A. 1994. Discrete Groups, Expanding Graphs and Invariant Measures. Birkhauser, Boston. \" · Zbl 0826.22012
[34]	MARGULIS, G. 1973. Explicit construction of concentrators. Problemy Peredachi Informatsii · Zbl 0312.22011
[35]	MICLO, L. 1995a. Sur les problemes de sortie discrets inhomogenes. · Zbl 0870.60062 · doi:10.1214/aoap/1035463326
[36]	MICLO, L. 1995b. Remarques sur l’hy percontractivite et l’evolution de l’entropie pour des \' ćhaines de Markov finies.
[37]	QUASTEL, J. 1992. Diffusion of colour in the simple exclusion process. Comm. Pure Appl. Math. 45 623 679. · Zbl 0769.60097 · doi:10.1002/cpa.3160450602
[38]	ROTHAUS, O. 1980. Logarithmic Sobolev inequalities and the spectrum of Sturm Liouville operators. J. Funct. Anal. 39 42 56. · Zbl 0472.47024 · doi:10.1016/0022-1236(80)90018-X
[39]	ROTHAUS, O. 1981. Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities. J. Funct. Anal. 42 102 109. · Zbl 0471.58027 · doi:10.1016/0022-1236(81)90049-5
[40]	ROTHAUS, O. 1981. Logarithmic Sobolev inequalities and the spectrum of Schrodinger öperators. J. Funct. Anal. 42 110 120. · Zbl 0471.58025 · doi:10.1016/0022-1236(81)90050-1
[41]	SARNACK, P. 1990. Some Applications of Modular Forms. Cambridge Univ. Press.
[42]	SINCLAIR, A. 1992. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing 1 351 370. · Zbl 0801.90039 · doi:10.1017/S0963548300000390
[43]	SINCLAIR, A. 1993. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser, Boston. \" · Zbl 0780.68096
[44]	STEIN, E. 1993. Harmonic Analy sis. Princeton Univ. Press. · Zbl 0821.42001
[45]	STEIN, E. and WEISS, G. 1971. Introduction to Fourier Analy sis on Euclidean Spaces. Princeton Univ. Press. · Zbl 0232.42007
[46]	STROOCK, D. 1993. Logarithmic Sobolev inequalities for Gibbs states. Lecture Notes in Math. 1563. Springer, Berlin. · Zbl 0801.60056 · doi:10.1007/BFb0074094
[47]	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 · doi:10.1007/BF02096629
[48]	SU, F. 1995. Ph.D. dissertation, Harvard Univ.
[49]	YAU, T. H. 1995. Logarithmic Sobolev inequality for zero range process. Report, Dept. Mathematics, New York Univ.
[50]	CNRS, UNIVERSITE PAUL SABATIER \' HARVARD UNIVERSITY STATISTIQUE ET PROBABILITES \' DEPARTMENT OF MATHEMATICS 31062 TOULOUSE CEDEX CAMBRIDGE, MASSACHUSETTS 02138 FRANCE EMAIL: lsc.cict.fr