Counting, sampling and integrating: algorithms and complexity

Publication date 19 March 2003

approximate counting colouring algorithm coupling Markov chain mixing time path coupling sampling approximately at random volume of convex body

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Markov processes (60Jxx) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Review text

This book is based on a postgraduate lecture course given by the author at ETH Zürich in 2000. (Notes taken and word-processed by the students were subsequently edited by the author to produce the book.) The topic is how difficult it is to enumerate the number of structures in a given object: for example, we might be trying to find the number of proper colourings of a given graph. The given objects will have size indexed by natural numbers \(n\) say -- in our example, the number of vertices of the graph -- and the key question is whether the number of structures can be counted efficiently. \textit{Efficiently} is taken to mean in time bounded by some polynomial in \(n\). Counting sometimes means counting exactly, but more often counting approximately (but with some rigorous guarantee on the size of the relative error) -- the relevant technical notion is a so-called FPRAS. Many of the ideas considered have applications to statistical physics. The purpose of the book is pedagogic and the author accordingly sometimes concentrates on illustrating notions by special cases which give the flavour, rather than getting bogged down in too many technicalities or proving the best possible result. The reviewer feels that this aspect has been very nicely handled. Chapter 1 presents two classical cases where the number of structures can be found exactly in polynomial time: spanning trees in an undirected graph (using Kirchoff's theorem) and perfect matchings in a planar graph. However it appears that most of the time exact enumeration is too much to hope for, so the rest of the book concentrates on approximate counting. The first observation, dealt with in Chapter 3, is that (subject to mild technical conditions) approximately counting structures is equivalent to sampling from the set of all such structures (almost) uniformly and at random. This reduces the problem to that of sampling. The main technique studied in these notes for sampling is the Markov chain Monte Carlo method. Basically one defines a certain Markov chain \((X_{t})\) whose stationary distribution is the distribution one wishes to sample from. For this approach to be successful, one needs to know how quickly the Markov chain converges to its stationary distribution: the key measure of this is the so-called mixing time of the chain, which one thus wishes to bound from above. One key technique for this is the coupling method of Döblin, popularised in the combinatorial context by D. J. Aldous and discussed in Chapter 4. Basically, one runs two copies of the Markov chain, \((X_{t})\) and \((Y_{t})\) which are correlated so as to make it likely that we will have \(X_{t}=Y_{t}\) for some small \(t\) (after which the two chains will be identical). If \(t(\varepsilon)\) is such that (irrespective of the two starting states) \[ P(X_{t(\varepsilon)}\neq Y_{t(\varepsilon)})\leq \varepsilon \] then \(t(\varepsilon)\) is an upper bound on the mixing time. The idea is illustrated by giving an FPRAS for counting proper \(q\)-colourings of a graph \(G\), provided \(q\geq 2\Delta+1\) where \(\Delta\) is the maximum degree of \(G\). Also discussed is Bubley and Dyer's notion of path coupling: the essential idea here is to define the coupling only on `adjacent' states of the chain, then extend to arbitrary pairs of states by composing couplings along a path. These notions of coupling do not always seem to be applicable to prove rapid mixing, so Chapter 5 studies the notion of canonical paths. Here the mixing time is bounded above by bounding a suitable notion of the congestion \(\rho\) of the Markov chain. The so-called Poincaré inequality shows that if \(\rho\) is small and the function has high global variation, then it has high local variation: the latter in turn implies rapid mixing. This is illustrated by giving an upper bound on the mixing time of an algorithm for sampling (weighted) matchings in a graph. In Chapter 6, the problem of sampling uniformly at random a point from a convex body \(K\) is discussed. Inevitably this is more technical than the previous examples -- (e.g. now the state space is continuous). In the `ball-walk'of Lovász and Simonovits, given \(X_{t}\) a point in the ball at time \(t\), \(X_{t+1}\) is chosen uniformly and at random from the intersection with \(K\) of the ball centred at \(X_{t}\) of radius \(\delta\). This is shown to have a stationary distribution, and mixing time polynomial in the dimension \(n\) of the space \(K\), provided \(\delta\) is judiciously chosen and \(K\) satisfies some technical conditions. An analogue of the Poincaré inequality plays a key role. Unsurprisingly, there are also some problems for which one cannot even approximately count the number of structures in polynomial time. Chapter 7 gives proofs that (unless implausible statements about complexity theory are true) there is no FPRAS for the number of Hamilton cycles in a graph \(G\) (crudely, because this would distinguish the non-zero from the zero case with reasonable probability) and there is no FPRAS for the number of independent sets (of all sizes) in a graph \(G\), even if we restrict its maximum degree to be (say) 1188 (this number can be sharpened to 25). For brevity, this review has suppressed the details of the complexity theory involved; these are filled in in Chapter 2. A slightly more expansive index would have been nice, but this is a very minor quibble about a book which will probably be very helpful to those trying to learn this material.

Recommendations

Cited in

(96)

This page was built for publication: Counting, sampling and integrating: algorithms and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4798347)