Evolving sets, mixing and heat kernel bounds

DOI10.1007/S00440-005-0434-7zbMATH Open1080.60071arXivmath/0305349OpenAlexW2028920027MaRDI QIDQ2571014

Author name not available (Why is that?)

Publication date: 2 November 2005

Published in: (Search for Journal in Brave)

Abstract: We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove that the bounds for mixing time in total variation obtained by Lovasz and Kannan, can be refined to apply to the maximum relative deviation

| p^{n} (x, y) / p i (y) - 1 |

of the distribution at time

n

from the stationary distribution

p i

. We then extend our results to Markov chains on infinite state spaces and to continuous-time chains. Our approach yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.

Full work available at URL: https://arxiv.org/abs/math/0305349

Mathematics Subject Classification ID

No records found.

This page was built for publication: Evolving sets, mixing and heat kernel bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2571014)