Making Markov chains less lazy

Details Making Markov chains less lazy Making Markov chains less lazy

2012-03-29

arxiv.org/abs/1203.6668v1

Mathematics

Combinatorics

26 pages

Scientific paper

The mixing time of an ergodic, reversible Markov chain can be bound in terms of the eigenvalues of the chain: specifically, the second-largest eigenvalue and the most negative eigenvalue. It has become standard to focus only on the second-largest eigenvalue, by making the Markov chain "lazy". (A lazy chain does nothing at each step with probability at least 1/2, and has only nonnegative eigenvalues.) We describe an approach which can be used to bound the most negative eigenvalue of an ergodic, reversible Markov chain. The new result is a modification of a proposition of Diaconis and Stroock from 1991 [Annals of Applied Probability 1 (1991), 36-61, Proposition 2] inspired by Sinclair's multicommodity flow approach to bounding the second-largest eigenvalue. Methods for comparing the mixing time of two Markov chains on the same state space are reviewed, as some of these provide a means of bounding the mixing time of a Markov chain without the assumption of laziness. The new result is compared with these existing approaches. By revisiting the analysis of three well-known combinatorial Markov chains, we demonstrate that it is often quite easy to obtain a bound on the most negative eigenvalue using the new result. Furthermore, the bound obtained is often much smaller than the corresponding bound on the second-largest eigenvalue, which results in the same bound on the mixing time (indeed, a factor of two smaller) without the imposition of laziness.

Affiliated with

Also associated with

No associations

Rating

Making Markov chains less lazy 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 Making Markov chains less lazy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Making Markov chains less lazy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-63618