PAINTING A GRAPH WITH COMPETING RANDOM WALKS

作者：Miller Jason^*

来源：Annals of Probability, 2013, 41(2): 636-670.

DOI：10.1214/11-AOP713

• Random walk
• competing random walks
• variance

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.

• 出版日期2013-3