Summary: Let \(X_1\), \(X_2\) be independent random walks on \({\mathbb{Z}}^d_n\), \(d \geq 3\), each starting from the uniform distribution. Initially, each site of \({\mathbb{Z}}^d_n\) 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 \({\mathbb{Z}}^d_n\) has been visited, is \(\frac{1}{2} n^d\) by symmetry. We prove the following conjecture due to Pemantle and Peres: for each \(d \geq 3\) there exists a constant \(\alpha_d\) such that
\[ \lim_{n\to\infty} \text{Var}\left(|{\mathcal A}_i|\right)/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 \geq 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 \(\text{Var}\left(|{\mathcal{A}}_i|\right)\) 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.