Evolving sets, mixing and heat kernel bounds
Evolving sets, mixing and heat kernel bounds
复制标题
演化集、混合和热核边界
DOI：
10.1007/s00440-005-0434-7
复制
发表时间：
2003
影响因子：
2
通讯作者：
Y. Peres
中科院分区：
文献类型：
--
作者：
Ben Morris;Y. Peres
我们表明，一个新的概率技术，最近推出的第一作者，产生最尖锐的边界上的马尔可夫链的混合时间的状态空间的等周性质（也被称为电导界或Cheeger不等式）。我们证明了Lovász和Kannan得到的全变分中混合时间的界可以被细化以适用于最大相对偏差|pn（x，y）/π（y）−1|从平稳分布π中分离出来。然后，我们将我们的结果扩展到无限状态空间上的马尔可夫链和连续时间链。我们的方法产生一个直接的联系等周不等式和热核边界，以前，这种联系依赖于分析估计称为纳什不等式。
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.