Evolving sets, mixing and heat kernel bounds

DOI10.1007/S00440-005-0434-7MaRDI QIDQ2571014zbMATH OpenOpenAlexFDO

Publication date 2 November 2005

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0305349

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Continuous-time Markov processes on discrete state spaces (60J27)

Abstract: We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove that the bounds for mixing time in total variation obtained by Lovasz and Kannan, can be refined to apply to the maximum relative deviation

| p^{n} (x, y) / p i (y) - 1 |

of the distribution at time

n

from the stationary distribution

p i

. We then extend our results to Markov chains on infinite state spaces and to continuous-time chains. Our approach yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.

Review text

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.

Recommendations

Cites work

Cited in

(61)

This page was built for publication: Evolving sets, mixing and heat kernel bounds

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