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 <math>\Phi_S</math> 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 <math>\Phi_S</math> over sets <math>S</math> that have a total stationary probability of at most 1/2. Conductance is related to Markov chain mixing time in the reversible setting.
References
- A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser, Boston-Basel-Berlin, 1993.
