Approximate counting, uniform generation and rapidly mixing Markov chains (Q1117955): Difference between revisions

The paper studies effective approximate solutions to combinatorial counting and uniform generation problems. Using a technique based on the simulation of ergodic Markov chains, it is shown that, for self-reducible structures, almost uniform generation is possible in polynomial time provided only that randomized approximate counting to within some arbitrary polynomial factor is possible in polynomial time. It follows that, for self-reducible structures, polynomial time randomized algorithms for counting to within factors of the form \((1+n^{-\beta})\) are available either for all \(\beta\in {\mathbb{R}}\) or for no \(\beta\in {\mathbb{R}}\). A substantial part of the paper is devoted to investigating the rate of convergence of finite ergodic Markov chains, and a simple but powerful characterization of rapid convergence for a broad class of chains based on a structural property of the underlying graph is established. Finally, the general techniques of the paper are used to derive an almost uniform generation procedure for labelled graphs with a given degree sequence which is valid over a much wider range of degrees than previous methods: this in turn leads to randomized approximate counting algorithms for these graphs with very good asymptotic behaviour.