Conductance (probability)

From Wikipedia, the free encyclopedia

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.