logo AFST
The logarithmic Sobolev constant of some finite Markov chains
Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 17 (2008) no. 2, pp. 239-290.

La constante de Sobolev logarithmic est toujours inférieure ou égale à la moitié du trou spectral. Il est naturel de se demander dans quels cas l’égalité à lieu. Nous considérons cette question dans le cadre des chaînes de Markov sur un espace fini de petite taille. En particulier, nous montrons l’égalité pour la marche aléatoire simple sur un cycle fini de 5 points et discutons plusieurs familles de chaînes sur 3 et 4 points.

The logarithmic Sobolev constant is always bounded above by half the spectral gap. It is natural to ask when this inequality is an equality. We consider this question in the context of reversible Markov chains on small finite state spaces. In particular, we prove that equality holds for simple random walk on the five cycle and we discuss assorted families of chains on three and four points.

Reçu le : 2006-11-15
Accepté le : 2007-02-01
Publié le : 2008-12-11
DOI : https://doi.org/10.5802/afst.1183
@article{AFST_2008_6_17_2_239_0,
     author = {Guan-Yu Chen and Wai-Wai Liu and Laurent Saloff-Coste},
     title = {The logarithmic Sobolev constant of some finite Markov chains},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {239--290},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 17},
     number = {2},
     year = {2008},
     doi = {10.5802/afst.1183},
     zbl = {1163.60319},
     mrnumber = {2487855},
     language = {en},
     url = {afst.centre-mersenne.org/item/AFST_2008_6_17_2_239_0/}
}
Guan-Yu Chen; Wai-Wai Liu; Laurent Saloff-Coste. The logarithmic Sobolev constant of some finite Markov chains. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 17 (2008) no. 2, pp. 239-290. doi : 10.5802/afst.1183. https://afst.centre-mersenne.org/item/AFST_2008_6_17_2_239_0/

[1] Ané (C.), Blachère (S.), Chafaï (D.), Fougères (P.), Gentil (I.), Malrieu (F.), Roberto (C.) and Scheffer (G.).— Sur les inégalités de Sobolev logarithmiques, volume 10 of Panoramas et Synthèses [Panoramas and Syntheses], Société Mathématique de France, Paris (2000). | MR 1845806 | Zbl 0982.46026

[2] Bakry (D.).— L’hypercontractivité et son utilisation en théorie des semigroups, In École d’été de Saint Flour 1992, volume 1581 of Lecture Note in Mathematics, Springer (1994). | Zbl 0856.47026

[3] Bakry (D.).— Remarques sur les semigroupes de Jacobi, Astérisque, (236), p. 23–39, Hommage à P. A. Meyer et J. Neveu (1996). | MR 1417973 | Zbl 0859.47026

[4] Bakry (D.) and Émery (M.).— Diffusions hypercontractive, In Séminaire de probabilité XIX, volume 1123 of Lecture Note in Mathematics, pages 179–206, Springer (1985). | Numdam | MR 889476 | Zbl 0561.60080

[5] Beckner (W.).— Inequalities in Fourier analysis, Ann. of Math., 102, p. 159–182 (1975). | MR 385456 | Zbl 0338.42017

[6] Benjamini (I.), Kalai (G.), and Schramm (O.).— First passage percolation has sublinear distance variance, Ann. Probab., 31, p. 1970–1978 (2003). | MR 2016607 | Zbl 1087.60070

[7] Berger (M.), Gauduchon (P.), and Mazet (E.).— Le spectre d’une variété riemannienne, volume 194 of Lecture Notes in Mathematics, Springer-Verlag, Berlin-New York (1971). | Zbl 0223.53034

[8] Bobkov (S.) and Tetali (P.).— Modified log-Sobolev inequalities, mixing and hypercontractivity, In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pages 287–296. ACM (2003). | MR 2120475

[9] Bonami (A.).— Étude des coefficients Fourier des fonctions de Lp(G), Ann. Inst. Fourier, 20, p. 335–402 (1970). | Numdam | MR 283496 | Zbl 0195.42501

[10] Chen (G.-Y.) and Sheu (Y.-C.).— On the log-Sobolev constant for the simple random walk on the n-cycle: the even cases, J. Funct. Anal., 202, p. 473–485 (2003). | MR 1990534 | Zbl 1028.60072

[11] Chung (F.).— Logarithmic Sobolev techniques for random walks on graphs, In Emerging applications of number theory (Minneapolis, MN, 1996), volume 109 of IMA Vol. Math. Appl., pages 175–186. Springer, New York (1999). | MR 1691531 | Zbl 0992.60072

[12] Chung (F.) and Yau (S.-T.).— Logarithmic Harnack inequalities. Math. Res. Lett., 3, p. 793–812 (1996). | MR 1426537 | Zbl 0880.58026

[13] Diaconis (P.) and Saloff-Coste (L.).— Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., 6, p. 695–750 (1996). | MR 1410112 | Zbl 0867.60043

[14] Émery (M.) and Yukich (J.).— A simple proof of the logarithmic Sobolev inequality on the circle. In Séminaire de Probabilités XXI, volume 1247 of Lecture Notes in Math., pages 173–175. Springer, Berlin (1987). | Numdam | MR 941981 | Zbl 0616.46023

[15] Frieze (A.) and Kannan (R.).— Log-Sobolev inequalities and sampling from log-concave distributions, Ann. Appl. Probab., 9, p. 14–26 (1999). | MR 1682608 | Zbl 0931.68140

[16] Gao (F.) and Quastel (J.).— Exponential decay of entropy in the random transposition and Bernoulli-Laplace models, Ann. Appl. Probab., 13, p. 1591–1600 (2003). | MR 2023890 | Zbl 1046.60003

[17] Goel (S.).— Modified logarithmic Sobolev inequalities for some models of random walk, Stochastic Process. Appl., 114, p. 51–79 (2004). | MR 2094147 | Zbl 1074.60080

[18] Gross (L.).— Logarithmic Sobolev inequalities, Amer. J. Math., 97, p. 1061–1083 (1976). | MR 420249 | Zbl 0318.46049

[19] Gross (L.).— Logarithmic Sobolev inequalities and contractivity properties of semigroups, In Dirichlet forms (Varenna, 1992), volume 1563 of Lecture Notes in Math., pages 54–88, Springer, Berlin (1993). | MR 1292277 | Zbl 0812.47037

[20] Houdré (C.).— Mixed and isoperimetric estimates on the log-Sobolev constants of graphs and Markov chains. Combinatorica, 21, p. 489–513, 2001. | MR 1863575 | Zbl 0989.05118

[21] Houdré (C.) and Tetali (P.).— Concentration of measure for products of Markov kernels and graph products via functional inequalities, Combin. Probab. Comput., 10, p. 1–28 (2001). | MR 1827807 | Zbl 0986.28004

[22] Jerrum (M.), Son (J-B.), Tetali (P.), and Vigoda (E.).— Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains, Ann. Appl. Probab., 14, p.1741–1765 (2004). | MR 2099650 | Zbl 1067.60065

[23] Korzeniowski (A.) and Stroock (D.).— An example in the theory of hypercontractive semigroups, Proc. A.M.S., 94, p. 87–90 (1985). | MR 781062 | Zbl 0577.47043

[24] Ledoux (M.).— Concentration of measure and logarithmic Sobolev inequalities, In Séminaire de Probabilités XXXIII, volume 1709 of Lecture Notes in Math., pages 120–216, Springer, Berlin (1999). | Numdam | MR 1767995 | Zbl 0957.60016

[25] Lee (T.-Y.) and Yau (H.-T.).— Logarithmic Sobolev inequality for some models of random walks. Ann. Probab., 26, p. 1855–1873 (1998). | MR 1675008 | Zbl 0943.60062

[26] Martinelli (F.).— Relaxation times of Markov chains in statistical mechanics and combinatorial structures, In Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 175–262, Springer, Berlin (2004). | MR 2023653 | Zbl pre02042289

[27] Mathieu (P.).— Log-Sobolev and spectral gap inequalities for the knapsack Markov chain, Markov Process. Related Fields, 8, p. 595–610 (2002). | MR 1957221 | Zbl 1028.60073

[28] Miclo (L.).— Remarques sur l’hypercontractivité et l’évolution de l’entropie pour des chaînes de Markov finies, In Séminaire de Probabilités XXXI, volume 1655 of Lecture Notes in Math., pages 136–167, Springer, Berlin (1997). | Numdam | Zbl 0882.60065

[29] Miclo (L.).— Monotonicité des fonctions extrémales pour les inégalités de type Sobolev logarithmiques en dimension 1, Preprint (2005).

[30] Mueller (C.) and Weissler (F.).— Hypercontractivity for the heat semigroup for ultraspherical polynomials and on the n-sphere, J. Funct. Anal., 48, p. 252–283, 1982. | MR 674060 | Zbl 0506.46022

[31] Nelson (E.).— The free Markov field, J. Funct. Anal., 12, p. 211–227 (1973). | MR 343816 | Zbl 0273.60079

[32] Rothaus (O.).— Logarithmic Sobolev inequalities and the spectrum of Sturm-Liouville operators, J. Funct. Anal., 39, p. 42–56 (1980). | MR 593787 | Zbl 0472.47024

[33] Rothaus (O.).— Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities, J. Funct. Anal., 42, p. 102–109 (1981). | MR 620581 | Zbl 0471.58027

[34] Rothaus (O.).— Logarithmic Sobolev inequalities and the spectrum of Schrödinger operators, J. Funct. Anal., 42, p. 110–120 (1981). | MR 620582 | Zbl 0471.58025

[35] Rothaus (O.).— Hypercontractivity and the Bakry-Émery criterion for compact Lie groups, J. Funct. Anal., 65, p. 358–367 (1986). | MR 826433 | Zbl 0589.58036

[36] Saloff-Coste (L.).— Precise estimates on the rate at which certain diffusions tend to equilibrium, Math. Zeit., 217, p. 641–677 (1994). | MR 1306030 | Zbl 0815.60074

[37] Saloff-Coste (L.).— Lectures on finite Markov chains, In Lectures on probability theory and statistics (Saint-Flour, 1996), volume 1665 of Lecture Notes in Math., pages 301–413, Springer, Berlin (1997). | MR 1490046 | Zbl 0885.60061

[38] Simon (B.).— A remark on Nelson’s best hypercontractivity estimates, Proc. Amer. Math. Soc., 55, p. 376–378 (1976). | Zbl 0441.46026

[39] Talagrand (M.).— Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem, Geom. Funct. Anal., 3, p. 295–314 (1993). | Zbl 0806.46035

[40] Weissler (F.).— Logarithmic Sobolev inequalities and hypercontractive estimates on the circle, J. Funct. Anal., 37, p. 218–234 (1980). | MR 578933 | Zbl 0463.46024