Algorithms for Random Generation and Counting: A Markov Chain Approach

Description

This monograph studies two classical computational problems: counting the elements of a finite set of combinatorial structures, and generating them at random from some probability distribution. Apart from their intrinsic interest, these problems arise naturally in many branches of mathematics and the natural sciences. The author aims to classify the computational difficulty of these problems for various naturally occurring structures: the emphasis is on positive results that demonstrate the existence of efficient algorithms. At the heart of the monograph is a single algorithmic paradigm; simulate a Markov chain whose states are combinatorial structures. A major portion of the monograph is devoted to developing new mathematical tools for the analysis of algorithms of this kind. Among the applications presented are the first provably efficient algorithms for several important counting and generation problems. Further applications are summarized in an appendix. This book will be of interest to researchers and graduate students in theoretical computer science, probability and statistics and theoretical physicists with an interest in Monte Carlo methods. It is a timely contribution to a fast moving field, with the immediacy and freshness of a new discovery.