Abstract
Motivated by (the rate of information loss or) the rate at which the entropy of an ergodic Markov chain relative to its stationary distribution decays to zero, we study modified versions of the standard logarithmic Sobolev inequality 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 also derive a hypercontractivity formulation equivalent to our main modified log-Sobolev inequality which might be of independent interest. Finally we show that, in contrast with the spectral gap, for bounded degree expander graphs various log-Sobolev-type constants go to zero with the size of the graph.
Original language | English (US) |
---|---|
Pages (from-to) | 287-296 |
Number of pages | 10 |
Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |
DOIs | |
State | Published - 2003 |
Event | 35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003 |
Keywords
- Entropy decay
- Sobolev Inequalities
- Spectral gap