Painting a graph with competing random walks

Abstract

Let $X_1,X_2$ be independent random walks on ${\mathbf{Z}}_n^d$, $d\ge 3$, each starting from the uniform distribution. Initially, each site of ${\mathbf{Z}}_n^d$ is unmarked, and, whenever $X_i$ visits such a site, it is set irreversibly to $i$. The mean of $|{\mathcal{A}}_i|$, the cardinality of the set ${\mathcal{A}}_i$ of sites painted by $i$, once all of ${\mathbf{Z}}_n^d$ has been visited, is $\frac{1}{2}{n}^d$ by symmetry. We prove the following conjecture due to Pemantle and Peres: for each $d\ge 3$ there exists a constant ${\alpha }_d$ such that ${\lim }_{n\to \infty }\mathrm{Var}(|{\mathcal{A}}_i|)/h_d(n)=\frac{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\ge 5$. We will also identify ${\alpha }_d$ explicitly and show that ${\alpha }_d\to 1$ as $d\to \infty$. This is a special case of a more general theorem which gives the asymptotics of $\mathrm{Var}(|{\mathcal{A}}_i|)$ 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.

Published in at http://dx.doi.org/10.1214/11-AOP713 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Late points for random walks in two dimensions
• Uniformity of the uncovered set of random walk and cutoff for lamplighter chains

Cited by in corpus (1)

• Fluctuation results for size of the vacant set for random walks on discrete torus