TR-2003-04
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.
Abstract
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
Comments are available on this technical report.
