The logarithmic Sobolev constant of some finite Markov chains

Guan-Yu Chen[1]; Wai-Wai Liu[2]; Laurent Saloff-Coste[3]

  • [1] Division of Mathematics, National Center for Theoretical Science, National Tsing Hua University, Hsinchu 300, Taiwa
  • [2] Stanford University, Department of Statistics, Stanford, CA 94305-4065
  • [3] Cornell University, Department of Mathematics, Ithaca, NY 14853-420

Annales de la faculté des sciences de Toulouse Mathématiques (2008)

  • Volume: 17, Issue: 2, page 239-290
  • ISSN: 0240-2963

Abstract

top
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.

How to cite

top

Chen, Guan-Yu, Liu, Wai-Wai, and Saloff-Coste, Laurent. "The logarithmic Sobolev constant of some finite Markov chains." Annales de la faculté des sciences de Toulouse Mathématiques 17.2 (2008): 239-290. <http://eudml.org/doc/10086>.

@article{Chen2008,
abstract = {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.},
affiliation = {Division of Mathematics, National Center for Theoretical Science, National Tsing Hua University, Hsinchu 300, Taiwa; Stanford University, Department of Statistics, Stanford, CA 94305-4065; Cornell University, Department of Mathematics, Ithaca, NY 14853-420},
author = {Chen, Guan-Yu, Liu, Wai-Wai, Saloff-Coste, Laurent},
journal = {Annales de la faculté des sciences de Toulouse Mathématiques},
language = {eng},
month = {6},
number = {2},
pages = {239-290},
publisher = {Université Paul Sabatier, Toulouse},
title = {The logarithmic Sobolev constant of some finite Markov chains},
url = {http://eudml.org/doc/10086},
volume = {17},
year = {2008},
}

TY - JOUR
AU - Chen, Guan-Yu
AU - Liu, Wai-Wai
AU - Saloff-Coste, Laurent
TI - The logarithmic Sobolev constant of some finite Markov chains
JO - Annales de la faculté des sciences de Toulouse Mathématiques
DA - 2008/6//
PB - Université Paul Sabatier, Toulouse
VL - 17
IS - 2
SP - 239
EP - 290
AB - 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 - eng
UR - http://eudml.org/doc/10086
ER -

References

top
  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). Zbl0982.46026MR1845806
  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). Zbl0856.47026
  3. Bakry (D.).— Remarques sur les semigroupes de Jacobi, Astérisque, (236), p. 23–39, Hommage à P. A. Meyer et J. Neveu (1996). Zbl0859.47026MR1417973
  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). Zbl0561.60080MR889476
  5. Beckner (W.).— Inequalities in Fourier analysis, Ann. of Math., 102, p. 159–182 (1975). Zbl0338.42017MR385456
  6. Benjamini (I.), Kalai (G.), and Schramm (O.).— First passage percolation has sublinear distance variance, Ann. Probab., 31, p. 1970–1978 (2003). Zbl1087.60070MR2016607
  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). Zbl0223.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). Zbl1192.60020MR2120475
  9. Bonami (A.).— Étude des coefficients Fourier des fonctions de Lp(G), Ann. Inst. Fourier, 20, p. 335–402 (1970). Zbl0195.42501MR283496
  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). Zbl1028.60072MR1990534
  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). Zbl0992.60072MR1691531
  12. Chung (F.) and Yau (S.-T.).— Logarithmic Harnack inequalities. Math. Res. Lett., 3, p. 793–812 (1996). Zbl0880.58026MR1426537
  13. Diaconis (P.) and Saloff-Coste (L.).— Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., 6, p. 695–750 (1996). Zbl0867.60043MR1410112
  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). Zbl0616.46023MR941981
  15. Frieze (A.) and Kannan (R.).— Log-Sobolev inequalities and sampling from log-concave distributions, Ann. Appl. Probab., 9, p. 14–26 (1999). Zbl0931.68140MR1682608
  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). Zbl1046.60003MR2023890
  17. Goel (S.).— Modified logarithmic Sobolev inequalities for some models of random walk, Stochastic Process. Appl., 114, p. 51–79 (2004). Zbl1074.60080MR2094147
  18. Gross (L.).— Logarithmic Sobolev inequalities, Amer. J. Math., 97, p. 1061–1083 (1976). Zbl0318.46049MR420249
  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). Zbl0812.47037MR1292277
  20. Houdré (C.).— Mixed and isoperimetric estimates on the log-Sobolev constants of graphs and Markov chains. Combinatorica, 21, p. 489–513, 2001. Zbl0989.05118MR1863575
  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). Zbl0986.28004MR1827807
  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). Zbl1067.60065MR2099650
  23. Korzeniowski (A.) and Stroock (D.).— An example in the theory of hypercontractive semigroups, Proc. A.M.S., 94, p. 87–90 (1985). Zbl0577.47043MR781062
  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). Zbl0957.60016MR1767995
  25. Lee (T.-Y.) and Yau (H.-T.).— Logarithmic Sobolev inequality for some models of random walks. Ann. Probab., 26, p. 1855–1873 (1998). Zbl0943.60062MR1675008
  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). Zbl1206.82058MR2023653
  27. Mathieu (P.).— Log-Sobolev and spectral gap inequalities for the knapsack Markov chain, Markov Process. Related Fields, 8, p. 595–610 (2002). Zbl1028.60073MR1957221
  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). Zbl0882.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. Zbl0506.46022MR674060
  31. Nelson (E.).— The free Markov field, J. Funct. Anal., 12, p. 211–227 (1973). Zbl0273.60079MR343816
  32. Rothaus (O.).— Logarithmic Sobolev inequalities and the spectrum of Sturm-Liouville operators, J. Funct. Anal., 39, p. 42–56 (1980). Zbl0472.47024MR593787
  33. Rothaus (O.).— Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities, J. Funct. Anal., 42, p. 102–109 (1981). Zbl0471.58027MR620581
  34. Rothaus (O.).— Logarithmic Sobolev inequalities and the spectrum of Schrödinger operators, J. Funct. Anal., 42, p. 110–120 (1981). Zbl0471.58025MR620582
  35. Rothaus (O.).— Hypercontractivity and the Bakry-Émery criterion for compact Lie groups, J. Funct. Anal., 65, p. 358–367 (1986). Zbl0589.58036MR826433
  36. Saloff-Coste (L.).— Precise estimates on the rate at which certain diffusions tend to equilibrium, Math. Zeit., 217, p. 641–677 (1994). Zbl0815.60074MR1306030
  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). Zbl0885.60061MR1490046
  38. Simon (B.).— A remark on Nelson’s best hypercontractivity estimates, Proc. Amer. Math. Soc., 55, p. 376–378 (1976). Zbl0441.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). Zbl0806.46035
  40. Weissler (F.).— Logarithmic Sobolev inequalities and hypercontractive estimates on the circle, J. Funct. Anal., 37, p. 218–234 (1980). Zbl0463.46024MR578933

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.