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.
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.
@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, Institut de Math\'ematiques},
address = {Toulouse},
volume = {Ser. 6, 17},
number = {2},
year = {2008},
doi = {10.5802/afst.1183},
mrnumber = {2487855},
zbl = {1163.60319},
language = {en},
url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1183/}
}
TY - JOUR AU - Guan-Yu Chen AU - Wai-Wai Liu AU - Laurent Saloff-Coste TI - The logarithmic Sobolev constant of some finite Markov chains JO - Annales de la Faculté des sciences de Toulouse : Mathématiques PY - 2008 SP - 239 EP - 290 VL - 17 IS - 2 PB - Université Paul Sabatier, Institut de Mathématiques PP - Toulouse UR - https://afst.centre-mersenne.org/articles/10.5802/afst.1183/ DO - 10.5802/afst.1183 LA - en ID - AFST_2008_6_17_2_239_0 ER -
%0 Journal Article %A Guan-Yu Chen %A Wai-Wai Liu %A Laurent Saloff-Coste %T The logarithmic Sobolev constant of some finite Markov chains %J Annales de la Faculté des sciences de Toulouse : Mathématiques %D 2008 %P 239-290 %V 17 %N 2 %I Université Paul Sabatier, Institut de Mathématiques %C Toulouse %U https://afst.centre-mersenne.org/articles/10.5802/afst.1183/ %R 10.5802/afst.1183 %G en %F 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, Serie 6, Volume 17 (2008) no. 2, pp. 239-290. doi : 10.5802/afst.1183. https://afst.centre-mersenne.org/articles/10.5802/afst.1183/
[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 | Zbl
[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
[3] Bakry (D.).— Remarques sur les semigroupes de Jacobi, Astérisque, (236), p. 23–39, Hommage à P. A. Meyer et J. Neveu (1996). | MR | Zbl
[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 | Zbl
[5] Beckner (W.).— Inequalities in Fourier analysis, Ann. of Math., 102, p. 159–182 (1975). | MR | Zbl
[6] Benjamini (I.), Kalai (G.), and Schramm (O.).— First passage percolation has sublinear distance variance, Ann. Probab., 31, p. 1970–1978 (2003). | MR | Zbl
[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
[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
[9] Bonami (A.).— Étude des coefficients Fourier des fonctions de Lp(G), Ann. Inst. Fourier, 20, p. 335–402 (1970). | Numdam | MR | Zbl
[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 | Zbl
[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 | Zbl
[12] Chung (F.) and Yau (S.-T.).— Logarithmic Harnack inequalities. Math. Res. Lett., 3, p. 793–812 (1996). | MR | Zbl
[13] Diaconis (P.) and Saloff-Coste (L.).— Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., 6, p. 695–750 (1996). | MR | Zbl
[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 | Zbl
[15] Frieze (A.) and Kannan (R.).— Log-Sobolev inequalities and sampling from log-concave distributions, Ann. Appl. Probab., 9, p. 14–26 (1999). | MR | Zbl
[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 | Zbl
[17] Goel (S.).— Modified logarithmic Sobolev inequalities for some models of random walk, Stochastic Process. Appl., 114, p. 51–79 (2004). | MR | Zbl
[18] Gross (L.).— Logarithmic Sobolev inequalities, Amer. J. Math., 97, p. 1061–1083 (1976). | MR | Zbl
[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 | Zbl
[20] Houdré (C.).— Mixed and isoperimetric estimates on the log-Sobolev constants of graphs and Markov chains. Combinatorica, 21, p. 489–513, 2001. | MR | Zbl
[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 | Zbl
[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 | Zbl
[23] Korzeniowski (A.) and Stroock (D.).— An example in the theory of hypercontractive semigroups, Proc. A.M.S., 94, p. 87–90 (1985). | MR | Zbl
[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 | Zbl
[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 | Zbl
[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
[27] Mathieu (P.).— Log-Sobolev and spectral gap inequalities for the knapsack Markov chain, Markov Process. Related Fields, 8, p. 595–610 (2002). | MR | Zbl
[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
[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 | Zbl
[31] Nelson (E.).— The free Markov field, J. Funct. Anal., 12, p. 211–227 (1973). | MR | Zbl
[32] Rothaus (O.).— Logarithmic Sobolev inequalities and the spectrum of Sturm-Liouville operators, J. Funct. Anal., 39, p. 42–56 (1980). | MR | Zbl
[33] Rothaus (O.).— Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities, J. Funct. Anal., 42, p. 102–109 (1981). | MR | Zbl
[34] Rothaus (O.).— Logarithmic Sobolev inequalities and the spectrum of Schrödinger operators, J. Funct. Anal., 42, p. 110–120 (1981). | MR | Zbl
[35] Rothaus (O.).— Hypercontractivity and the Bakry-Émery criterion for compact Lie groups, J. Funct. Anal., 65, p. 358–367 (1986). | MR | Zbl
[36] Saloff-Coste (L.).— Precise estimates on the rate at which certain diffusions tend to equilibrium, Math. Zeit., 217, p. 641–677 (1994). | MR | Zbl
[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 | Zbl
[38] Simon (B.).— A remark on Nelson’s best hypercontractivity estimates, Proc. Amer. Math. Soc., 55, p. 376–378 (1976). | Zbl
[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
[40] Weissler (F.).— Logarithmic Sobolev inequalities and hypercontractive estimates on the circle, J. Funct. Anal., 37, p. 218–234 (1980). | MR | Zbl
Cited by Sources: