Algorithms for random generation and counting: a Markov chain approach (Q3135094)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 420886
Language Label Description Also known as
default for all languages
No label defined
    English
    Algorithms for random generation and counting: a Markov chain approach
    scientific article; zbMATH DE number 420886

      Statements

      0 references
      22 September 1993
      0 references
      simulation
      0 references
      rapid mixing
      0 references
      combinatorial structures
      0 references
      Markov chains
      0 references
      conductance
      0 references
      permanents
      0 references
      Algorithms for random generation and counting: a Markov chain approach (English)
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references