Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains

By M. Jerrum, Jung-Bae Son, Prasad Tetali, Eric Vigoda. 2004

116 citations recorded by the source corpus.

We consider finite-state Markov chains that can be naturally decomposed into smaller ``projection'' and ``restriction'' chains. Possibly this decomposition will be inductive, in that the restriction chains will be smaller copies of the initial chain. We provide expressions for Poincare (resp. log-Sobolev) constants of the initial Markov chain in terms of Poincare (resp. log-Sobolev) constants of the projection and restriction chains, together with further a parameter. In the case of the Poincare constant, our bound is always at least as good as existing ones and, depending on the value of the extra parameter, may be much better. There appears to be no previously published decomposition result for the log-Sobolev constant. Our proofs are elementary and self-contained.

Subfields: Mathematical Physics, Molecular Biology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/13d5ce5fc80896e2541f57991a2f83660bfc4349

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

1. Andreas Eberle
2. Mateusz B. Majka
3. Arnaud Guillin
4. Feng-Yu Wang
5. Raphael Zimmer
6. Patrick Cattiaux

In Statistics and Probability

1. Mateusz B. Majka
2. Andreas Eberle
3. Arnaud Guillin
4. Feng-Yu Wang
5. Raphael Zimmer
6. Patrick Cattiaux

Citations in the corpus

• Quantitative contraction rates for Markov chains on general state spaces (2018, background): “1 Introduction In recent years, convergence bounds for Markov processes in Kantorovich (L(1) Wasserstein) distances have emerged as a powerful alternative to more traditional approaches based on the total variation distance [36], spectral gaps and L(2) bounds [27, 9, 10], or entropy estimates [27, 9”