Mixing Time Bounds via the Spectral Profile

Details Mixing Time Bounds via the Spectral Profile Mixing Time Bounds via the Spectral Profile

2005-05-31

arxiv.org/abs/math/0505690v1

Mathematics

Probability

26 pages

Scientific paper

On complete, non-compact manifolds and infinite graphs, Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel. We develop this technique in the setting of finite Markov chains, proving upper and lower mixing time bounds via the spectral profile. This approach lets us recover and refine previous conductance-based bounds of mixing time (including the Morris-Peres result), and in general leads to sharper estimates of convergence rates. We apply this method to several models including groups with moderate growth, the fractal-like Viscek graphs, and the torus, to obtain tight bounds on the corresponding mixing times.

Affiliated with

Also associated with

No associations

Rating

Mixing Time Bounds via the Spectral Profile 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 Mixing Time Bounds via the Spectral Profile, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mixing Time Bounds via the Spectral Profile will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455766