Conductance (probability)

From Wikipedia, the free encyclopedia

You have new messages (last change).

For an ergodic reversible Markov Chain with an underlying graph G, the conductance is a way to measure how hard it is to leave a small set of nodes. Writing ΦS for the conditional probability of leaving a set of nodes S given that we were in that set to begin with, then the conductance is defined as the minimal ΦS over sets S that have a total stationary probability of at most 1/2. Conductance is related to Markov chain mixing time in the reversible setting.

[edit] See also

[edit] References

  • A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser, Boston-Basel-Berlin, 1993.
Retrieved from "http://en.wikipedia.org../../../c/o/n/Conductance_%28probability%29.html"