Algorithms for random generation and counting: a Markov chain approach

From MaRDI portal





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.




Cited in
(only showing first 100 items - show all)








This page was built for publication: Algorithms for random generation and counting: a Markov chain approach

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