scientific article; zbMATH DE number 18982

From MaRDI portal
Publication:3976407





[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.




Cited in
(25)








This page was built for publication:

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