Name
Abstract | ||
|---|---|---|
We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make our 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 *** r n ln n , where *** r = (r *** 1)/(r *** 2). In this paper we prove the following (whp) results. For k independent walks on a random regular graph G , the cover time C G (k ) is asymptotic to C G /k , where C G is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is $\theta_r n/\binom{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*** r n (ln k )/k , 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 (2ln 2) *** r n 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 expected time for all the particles to coalesce, which is asymptotic to 2 *** r n . Combining results from the predator-prey and multiple random walk models allows us to compare expected detection time in the following cops and robbers 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 *** r H *** n /k , where H *** is the ***-th harmonic number. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02930-1_33 | ICALP (2) |
Keywords | Field | DocType |
interacting particle systems,c g,k predator,k explosive particle,random regular graph,cover time c g,expected time,ln k,detection time,cover time,k independent walk,multiple random walks,harmonic number,interacting particle system,random walk,regular graph | Discrete mathematics,Random regular graph,Particle system,Combinatorics,Vertex (geometry),Random walk,Harmonic number,Expected value,Regular graph,Voter model,Mathematics | Conference |
Volume | ISSN | Citations |
5556 | 0302-9743 | 7 |
PageRank | References | Authors |
0.68 | 11 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 857 | 91.88 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Tomasz Radzik | 3 | 1098 | 95.68 |