Evolving sets, mixing and heat kernel bounds

Details Evolving sets, mixing and heat kernel bounds Evolving sets, mixing and heat kernel bounds

2003-05-25

arxiv.org/abs/math/0305349v2

Mathematics

Probability

21 pages, 4 figures, to appear in PTRF

Scientific paper

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)/\pi(y)-1|$ of the distribution at time $n$ from the stationary distribution $\pi$. 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.

Affiliated with

Also associated with

No associations

Rating

Evolving sets, mixing and heat kernel bounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Evolving sets, mixing and heat kernel bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Evolving sets, mixing and heat kernel bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-713826