Evolving sets, mixing and heat kernel bounds (Q2571014)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Evolving sets, mixing and heat kernel bounds |
scientific article |
Statements
Evolving sets, mixing and heat kernel bounds (English)
0 references
2 November 2005
0 references
Suppose \(\{p(x, y)\}\) are the transition probabilities of an irreducible Markov chain on a countable state space \(V\). If \(\pi\) is the stationary distribution of the chain, then it is of interest to study the following quantity which is called \(\varepsilon\)-uniform mixing time: \[ \tau(\varepsilon)= \min\Biggl\{n:\Biggl|{p^n(x,y)- \pi(y)\over \pi(y)}\Biggr|\leq \varepsilon\;\forall x,y\in V\Biggr\}. \] The authors use new probabilistic techniques allowing to derive new and efficient bounds for \(\tau(\varepsilon)\). The bounds are essential improvements of some previously known results in this area. One of the results, Theorem 1, tells us the following: Given a small positive \(\varepsilon\) and a stationary distribution \(\pi\), one can find an integer \(n_0\) which is of an integral form (we do not write details here), such that for all \(n\geq n_0\), we have \(|(p^n(x,y)- \pi(y))/\pi(y)|\leq\varepsilon\) uniformly in \(x\), \(y\). Several other related results are established. Among them are characterizations of the so-called evolving set processes and their relationship with the conductance profile of the chain. Four random walk examples are given and they illustrate well the rate of mixing times. Extensions are also provided for continuous-time Markov chains with finite state by deriving delicate heat kernel bounds for the rate of \(\varepsilon\)-mixing times. The questions treated in this paper and the results are clearly described and formulated. Detailed proofs, ideas and techniques are also provided. Finally, the four pages of concluding remarks explicitly outline possibilities for further studies in this interesting area.
0 references
0 references