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
26 June 1992
0 references
strongly aperiodic Markov chain
0 references
rapidly mixing
0 references
measure of connectedness
0 references
0.8650132417678833
0 references
0.8601210713386536
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