Convergence of mixing times for sequences of random walks on finite graphs
Convergence of mixing times for sequences of random walks on finite graphs
复制标题
DOI：
10.1214/ejp.v17-1705
复制
发表时间：
2011-11
影响因子：
1.4
通讯作者：
D. Croydon;B. Hambly;T. Kumagai
中科院分区：
文献类型：
--
作者：
D. Croydon;B. Hambly;T. Kumagai
在图序列上建立了保证图上随机游动的混合时间收敛的条件。主要的假设是图、相关测度和热核在适当的Gromov-Hausdorff意义下收敛。利用这一结果，我们建立了ErdőS-Renyi随机图的最大分量在临界窗口内的混合时的收敛性质，改进了以往关于该随机图模型的结果。我们的结果还使我们能够在许多其他例子中建立收敛，例如有限分枝分形图、Galton-Watson树和高维随机游动的值域。
We establish conditions on sequences of graphs which ensure that the mixing times of the random walks on the graphs in the sequence converge. The main assumption is that the graphs, associated measures and heat kernels converge in a suitable Gromov-Hausdorff sense. With this result we are able to establish the convergence of the mixing times on the largest component of the Erdős-Renyi random graph in the critical window, sharpening previous results for this random graph model. Our results also enable us to establish convergence in a number of other examples, such as finitely ramified fractal graphs, Galton-Watson trees and the range of a high-dimensional random walk.