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

Mark Jerrum; Jung-Bae Son; Prasad Tetali; Eric Vigoda. 9 March, 2003.
Communicated by Eric Vigoda.


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 Poincar\'e (respectively, log-Sobolev) constants of the initial Markov chain in terms of Poincar\'e (respectively, log-Sobolev) constants of the projection and restriction chains, together with further parameter. In the case of the Poincar\'e 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.

Original Document

The original document is available in PDF (uploaded 9 March, 2003 by Eric Vigoda).


Comments are available on this technical report.