Evolving sets, mixing and heat kernel bounds
By Ben Morris, Yuval Peres. 2003
153 citations recorded by the source corpus.
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 Lovász and Kannan, can be refined to apply to the maximum relative deviation |pn(x,y)/π(y)−1| of the distribution at time n from the stationary distribution π. 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.
Subfields: Molecular Biology, Statistics and Probability
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Molecular Biology
- Marek Tomasz Biskup
- Noam Berger
- Prasad Tetali
- Ravi Montenegro
- Raef Bassily
- Abhradeep Thakurta
- Adam D. Smith
- Sharad Goel
In Statistics and Probability
- Abhradeep Thakurta
- Raef Bassily
- Russell Lyons
- Marek Tomasz Biskup
- Yuval Peres
- Noam Berger
- Adam D. Smith
- Prasad Tetali
Citations in the corpus
- Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, methodology): “Towards this end, we use the result of [38] on the rapid mixing of lazy Markov chains with finite state space.”
- Probability on Trees and Networks (2017, background): “14, and a full proof can be found in Mörters and Peres (2010), Theorem 9.”
- A note on percolation on $Z^d$: isoperimetric profile via exponential cluster repulsion (2007, background): “We are going to show that there exist a constant c = c(Wh) ∈ (0, 1) and some k = k(S) ∈ Z+ such that w ≥ c √ h(k)v (5.1) and w ≥ v/k .”
- Mixing Time Bounds via the Spectral Profile (2005, methodology): “In contrast, the bound of Morris and Peres [ MP ] is”
- Quenched invariance principle for simple random walk on percolation clusters (2005, methodology): “Yuval Peres suggested the following generalization of Conjecture 1: Question 2.”