file.pdf (288.37 kB)
Download file

Multiple Random Walks in Random Regular Graphs

Download (288.37 kB)
journal contribution
posted on 01.06.2009, 00:00 by Colin Cooper, Alan FriezeAlan Frieze, Tomasz Radzik

We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs.

The cover time of a random walk on a random r-regular graph was studied in [6], where it was shown with high probability (whp), that for r ≥ 3 the cover time is asymptotic to θrn ln n, where θr = (r − 1)/(r − 2).

In this paper we prove the following (whp) results, arising from the study of multiple random walks on a random regular graph G. For k independent walks on G, the cover time CG(k) is asymptotic to CG/k, where CG is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is θrn/(k/2). If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for k walks to broadcast a single piece of information to each other is asymptotic to 2 ln k k θrn, as k, n → ∞.

We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing, or by annihilating each other. For example, the expected extinction time of k explosive particles (k even) tends to (2 ln 2)θrn as k → ∞.

The case of n coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbour. The expected time for a unique opinion to emerge is the same as the expected time for all the particles to coalesce, which is asymptotic to 2θrn.

Combining results from the predator-prey and multiple random walk models allows us to compare expected detection time of all prey in the following scenarios: both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, the predators move randomly and the prey stays fixed. In all cases, with k predators and ℓ prey the expected detection time is θrHℓn/k, where Hℓ is the ℓ-th harmonic number.


Publisher Statement

Copyright © 2009 Society for Industrial and Applied Mathematics



Usage metrics