No label defined (Q3976407)

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 18982
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 18982

      Statements

      0 references
      26 June 1992
      0 references
      strongly aperiodic Markov chain
      0 references
      rapidly mixing
      0 references
      measure of connectedness
      0 references
      [For the entire collection see Zbl 0733.00020.] Let \(X_ t\), \(t\in N\), be an irreducible, strongly aperiodic Markov chain on a finite state space with \(N\) elements. If \(p_{i,t}\) is the distribution of the chain at time \(t\), and \(\pi_ i\) the stationary distribution, let \(d_ 1(t)=\sum^ N_{i=1}| p_{i,t}-\pi_ i|\). The Markov chain \(X\) is said to be rapidly mixing if \(d_ 1(t)\leq\varepsilon\) for \(t=P(\log N)\log(1/\varepsilon)\), for some polynomial \(P\). This paper is a survey of new methods for proving rapid mixing properties for Markov chains. One of the methods discussed relies on the conductance of the chain, a certain measure of connectedness. The author shows how to bound the mixing time of the chain in terms of the conductance. Methods for lower-bounding the conductance, more combinatorial in nature, are also explained.
      0 references

      Identifiers