scientific article; zbMATH DE number 18982
[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.
- On the conductance of order Markov chains
- Relaxation of product Markov chains on product spaces
- A rapidly mixing stochastic system of finite interacting particles on the circle
- Exact mixing in an unknown Markov chain
- Speeding up Markov chains with deterministic jumps
- Evolving sets, mixing and heat kernel bounds
- Lifting Markov chains to speed up mixing
- Faster mixing via average conductance
- Rapid mixing and Markov bases
- Concentration of measure and mixing for Markov chains
- Some problems on approximate counting in graphs and matroids
- Mixing Markov Chains and Their Images
- Mathematical aspects of mixing times in Markov chains.
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- scientific article; zbMATH DE number 1789923 (Why is no real title available?)
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Mixing of permutations by biased transposition
- Vertex and edge expansion properties for rapid mixing
- scientific article; zbMATH DE number 1426485 (Why is no real title available?)
- Edge isoperimetry and rapid mixing on matroids and geometric Markov chains
- Blocking Conductance and Mixing in Random Walks
- Intersection conductance and canonical alternating paths: methods for general finite Markov chains
- Fast mixing of a randomized shift-register Markov chain
- Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
- Faster mixing and small bottlenecks
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)