Rapid mixing in Markov chains

Details Rapid mixing in Markov chains Rapid mixing in Markov chains

2003-04-28

arxiv.org/abs/math/0304470v1

Proceedings of the ICM, Beijing 2002, vol. 3, 673--684

Mathematics

Probability

Scientific paper

A wide class of ``counting'' problems have been studied in Computer Science. Three typical examples are the estimation of - (i) the permanent of an $n\times n$ 0-1 matrix, (ii) the partition function of certain $n-$ particle Statistical Mechanics systems and (iii) the volume of an $n-$ dimensional convex set. These problems can be reduced to sampling from the steady state distribution of implicitly defined Markov Chains with exponential (in $n$) number of states. The focus of this talk is the proof that such Markov Chains converge to the steady state fast (in time polynomial in $n$). A combinatorial quantity called conductance is used for this purpose. There are other techniques as well which we briefly outline. We then illustrate on the three examples and briefly mention other examples.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-334032