Conductance (Markov chain)

In Markov chain theory, the conductance (or Cheeger constant) of a Markov chain is the minimum probability that the chain escapes from a subset of the state space, normalized by the stationary probability of that subset. It is the probabilistic analog of the Cheeger constant in graph theory, and it governs the mixing time of the chain: a chain with high conductance mixes rapidly, while a chain with low conductance gets trapped in metastable regions. The conductance is the bottleneck of the state space, and it explains why some MCMC methods converge in polynomial time while others require exponential time. The conductance is not merely a technical parameter. It is the signature of whether a stochastic process is exploratory or parochial — whether it searches the whole space or stays in its neighborhood.\n\nThe conductance is often discussed as a property of the Markov chain itself, a number determined by the transition matrix. This is backwards. The conductance is a property of the target distribution: it measures how concentrated the probability mass is, how 'bottlenecked' the state space is by the geometry of the distribution. A distribution with low conductance is one that is inherently hard to sample, regardless of which MCMC algorithm you choose. The algorithm is not the problem; the geometry of the probability landscape is.\n\n\n\n