MEAN FIELD CONDITIONS FOR COALESCING RANDOM WALKS

被引:28
作者
Oliveira, Roberto Imbuzeiro [1 ]
机构
[1] IMPA, Rio De Janeiro, RJ, Brazil
关键词
Coalescing random walks; voter model; hitting times; exponential approximation; PERCOLATION; TIME;
D O I
10.1214/12-AOP813
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
The main results in this paper are about the full coalescence time C of a system of coalescing random walks over a finite graph G. Letting m(G) denote the mean meeting time of two such walkers, we give sufficient conditions under which E[C] approximate to 2m(G) and C/m(G) has approximately the same law as in the "mean field" setting of a large complete graph. One of our theorems is that mean field behavior occurs over all vertex-transitive graphs whose mixing times are much smaller than m(G); this nearly solves an open problem of Aldous and Fill and also generalizes results of Cox for discrete tori in d >= 2 dimensions. Other results apply to nonreversible walks and also generalize previous theorems of Durrett and Cooper et al. Slight extensions of these results apply to voter model consensus times, which are related to coalescing random walks via duality. Our main proof ideas are a strengthening of the usual approximation of hitting times by exponential random variables, which give results for non-stationary initial states; and a new general set of conditions under which we can prove that the hitting time of a union of sets behaves like a minimum of independent exponentials. In particular, this will show that the first meeting time among k random walkers has mean approximate to m(G)/((k)(2)).
引用
收藏
页码:3420 / 3461
页数:42
相关论文
共 16 条
[11]   Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters [J].
Leskovec, Jure ;
Lang, Kevin J. ;
Dasgupta, Anirban ;
Mahoney, Michael W. .
INTERNET MATHEMATICS, 2009, 6 (01) :29-123
[12]  
Levin DA., 2008, Markov Chains and Mixing Times, DOI DOI 10.1090/MBK/058
[13]  
Liggett T. M., 1985, GRUNDLEHREN MATH WIS, V276, DOI [10.1007/978-1-4613-8542-4, DOI 10.1007/978-1-4613-8542-4]
[14]   ON THE COALESCENCE TIME OF REVERSIBLE RANDOM WALKS [J].
Oliveira, Roberto Imbuzeiro .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2012, 364 (04) :2109-2128
[15]   A note on percolation on Zd:: Isoperimetric profile via exponential cluster repulsion [J].
Pete, Gabor .
ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2008, 13 :377-392
[16]  
PRATA A, 2012, THESIS IMPA RIO DE J