Conductance (probability)
Encyclopedia : C : CO : CON : Conductance (probability)
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. Conductance is tied to mixing time of ergodic reversible Markov Chains. If we define [\Phi_S] as the conditional probability of leaving a set of nodes S given that we were in that set to begin with then the conductance is the minimal [\Phi_S] over sets [S] that have a total stationary probability of at most 1/2.
See also
References
- A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser, Boston-Basel-Berlin, 1993.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.