Algorithms for random generation and counting: a Markov chain approach. (English) Zbl 0780.68096

Sinclair, Alistair

Progress in Theoretical Computer Science. Boston, MA: Birkhäuser. viii, 146 p. (1993).

This monograph studies the counting and random generation of finite sets of combinatorial structures. A single algorithmic paradigm is used: Simulate a discrete-time Markov chain \(X=\{X_ t\}^ \infty_{t=0}\) whose states are combinatorial structures. Preferably \(X\) should be set up to be ergodic and time-reversible any conveniently chosen state and to simulate \(X\) until a time \(t\) when \(X_ t\) is uniformly within a prescribed number \(\epsilon >0\) of the stationary distribution. Moreover, the class of Markov chains associated with all instances \(x\) of a particular combinatorial problem should be rapidly mixing, which essentially means that the time \(t\) above can be calculated as a polynomially bounded function of \(\epsilon\) and of the “complexity” of \(x\).
The key problem is to ensure rapid mixing, which the author relates to a more accessible feature of the Markov chain called its conductance. This defined to be the minimum of the conditional probabilities \(P(X_ 1\in S\backslash/E \mid X_ 0\in E)\), where \(X_ 0\) is taken to have the stationary distribution of the chain, where \(S\) denotes the state space, and where \(E\subseteq S\) is such that \(P(X_ 0\in E)\leq 1/2\). The use of conductance enables the author to obtain, for example, an efficient (i.e. polynomial-time) algorithm to approximate the permanent of a sufficiently “dense” matrix with \(0-1\) entries.
While tighter time bounds, and hence greater efficiency, can be obtained for some combinatorial problems using other methods such as coupling, stopping times and group representation theory, the author’s Markov chain method also applies to problems (e.g. the calculation of permanents) which are not amenable to analysis by any of the established methods. Moreover, if one is content with approximate counting and almost uniform generation, the method can treat an even wider class of problems in polynomial time.

Reviewer: B.K.Horkelheimer (Clayton)

MSC:

68R05	Combinatorics in computer science
68U20	Simulation (MSC2010)
60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
60J20	Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
15A15	Determinants, permanents, traces, other special matrix functions
65C99	Probabilistic methods, stochastic differential equations
65F20	Numerical solutions to overdetermined systems, pseudoinverses
65F50	Computational methods for sparse matrices

Keywords:

simulation; rapid mixing; combinatorial structures; Markov chains; conductance; permanents