Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

Most algorithmic problems could be viewed as questions being asked about a natural binary relation and we can classify them into decision, search, uniform generation and counting. For some relations, counting and uniform generation could be NP-Hard even if decision or search could be done efficiently. M. Jerrum and A. Sinclair used the Markov chain Monte Carlo method to approximately count the number of perfect matchings of a dense bipartite graph. They reduced approximate counting to almost uniform generation of perfect matchings. Almost uniform generation was done by starting with an arbitrary solution, and repeatedly making random modifications to it. This process was modeled as a Markov chain, with a stationary distribution that is uniform on the set of perfect matchings. The rapid convergence of the chain towards its stationary distribution, was proved by bounding a quantity called conductance. This was done using a novel method of defining canonical paths between every pair of states in the chain.