Coloring of a one-dimensional lattice by two independent random walkers

A new type of question in random walk theory is formulated and solved for the particular case of a periodic one-dimensional lattice. A “red” and a “blue” random walker perform simultaneous independent simple random walk. Each site is initially uncolored and takes irreversibly the color, red or blue, of the first walker by which it is visited. We study the resulting coloring of the final state, in which each site is either red or blue, on a ring of L sites. We calculate the probability P(n, L) that site n is red, in the scaling limit L → ∞ with n/L fixed, for walkers initially on diametrically opposite sites. We determine by simulation the number of interfaces (that is, pairs of neighboring red and blue sites), for initial separation a between the walkers. This number is ≈ 2.5 for initially diametrically opposite walkers, and appears to increase logarithmically with L/a.