PAINTING A GRAPH WITH COMPETING RANDOM WALKS

• 成果类型: Article
• 署名作者: Miller, Jason
• 署名单位: Stanford University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/11-AOP713
• 发表日期: 2013
• 页码: 636-670
• 关键词: random interlacements; brownian-motion; 2 dimensions; lattice; points; chains; range; set

摘要

Let X-1, X-2 be independent random walks on Z(n)(d), d >= 3, each starting from the uniform distribution. Initially, each site of Z(n)(d) is unmarked, and, whenever X-i visits such a site, it is set irreversibly to i. The mean of vertical bar A(i)vertical bar, the cardinality of the set A(i) of sites painted by i, once all of Z(n)(d) has been visited, is 1/2n(d) by symmetry. We prove the following conjecture due to Pemantle and Peres: for each d >= 3 there exists a constant alpha(d) such that lim(n ->infinity) Var(vertical bar A(i)vertical bar)/h(d)(n) = 1/4 alpha(d) where h(3)(n) = n(4), h(4)(n) = n(4)(log n) and h(d)(n) = n(d) for d >= 5. We will also identify alpha(d) explicitly and show that alpha(d) -> 1 as d -> infinity. This is a special case of a more general theorem which gives the asymptotics of Var(vertical bar A(i)vertical bar) for a large class of transient, vertex transitive graphs; other examples include the hypercube and the Caley graph of the symmetric group generated by transpositions.