Abstract
Motivated by the rate at which the entropy of an ergodic Markov chain relative to its stationary distribution decays to zero, we study modified versions of logarithmic Sobolev inequalities in the discrete setting of finite Markov chains and graphs. These inequalities turn out to be weaker than the standard log-Sobolev inequality, but stronger than the Poincare' (spectral gap) inequality. We show that, in contrast with the spectral gap, for bounded degree expander graphs, various log-Sobolev constants go to zero with the size of the graph. We also derive a hypercontractivity formulation equivalent to our main modified log-Sobolev inequality. Along the way we survey various recent results that have been obtained in this topic by other researchers.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 289-336 |
| Number of pages | 48 |
| Journal | Journal of Theoretical Probability |
| Volume | 19 |
| Issue number | 2 |
| DOIs | |
| State | Published - Jun 2006 |
Bibliographical note
Funding Information:We thank L. Saloff-Coste for providing us with several relevant references. We also thank the anonymous referees for a very careful reading of our manuscript. Research supported in part by NSF Grants DMS-0103929, DMS-0405587 (Sergey G. Bobkov) Research supported in part by NSF Grants DMS-0100298, DMS-0401239; research done while visiting Microsoft Research (Prasad Tetali)
Keywords
- Entropy decay
- Logarithmic Sobolev Inequalities
- Spectral gap