Painting a Graph with Competing Random Walks

Details Painting a Graph with Competing Random Walks Painting a Graph with Competing Random Walks

2010-03-10

arxiv.org/abs/1003.2168v1

Mathematics

Probability

34 pages, 3 figures

Scientific paper

Let $X_1, X_2$ be independent random walks on $\Z_n^d$, $d \geq 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 $|\CA_i|$, the cardinality of the set $\CA_i$ of sites painted by $i$ once all of $\Z_n^d$ has been visited, is $n^d/2$ 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} \var(|\CA_i|) / h_d(n) = \tfrac{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. This is a special case of a more general theorem which gives the asymptotics of $\var(|\CA_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.

Affiliated with

Also associated with

No associations

Rating

Painting a Graph with Competing Random Walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Painting a Graph with Competing Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Painting a Graph with Competing Random Walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-342438