Name
Abstract | ||
|---|---|---|
We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times 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 |pn(x,y)/π(y)-1| of the distribution at time n from the stationary distribution π. Our approach also yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1145/780542.780585 | STOC |
Keywords | DocType | ISBN |
nash inequality,isoperimetric property,heat kernel bound,direct link,stationary distribution,time n,analytic estimate,conductance bound,evolving set,isoperimetric inequality,cheeger inequality,mixing time,markov chain,total variation,state space,conductance,martingale,heat kernel,mcmc | Conference | 1-58113-674-9 |
Citations | PageRank | References |
5 | 0.67 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ben Morris | 1 | 127 | 8.78 |
| Yuval Peres | 2 | 523 | 53.68 |