Search

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 [C. Cooper and A. Frieze, SIAM J. Discrete Math., 18 (2005), pp. 728-740], 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/(2k). 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 2lnk/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 (2ln2)θ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 neighbor. 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 times of all prey in the following scenarios: Both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, and 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. [ABSTRACT FROM AUTHOR]

Abstract: Random walks in graphs have been applied to various network exploration and network maintenance problems. In some applications, however, it may be more natural, and more accurate, to model the underlying network not as a graph but as a hypergraph, and solutions based on random walks require a notion of random walks in hypergraphs. At each step, a random walk on a hypergraph moves from its current position to a random vertex in a randomly selected hyperedge containing . We consider two definitions of cover time of a hypergraph . If the walk sees only the vertices it moves between, then the usual definition of cover time, , applies. If the walk sees the complete edge during the transition, then an alternative definition of cover time, the inform time is used. The notion of inform time models passive listening which fits the following types of situations. The particle is a rumour passing between friends, which is overheard by other friends present in the group at the same time. The particle is a message transmitted randomly from location to location by a directional transmission in an ad-hoc network, but all receivers within the transmission range can hear. In this paper we give an expression for which is tractable for many classes of hypergraphs, and calculate and exactly for random -regular, -uniform hypergraphs. We find that for such hypergraphs, whp, , if . For random -regular, -uniform multi-hypergraphs, constant , and , we also prove that, whp, , i.e. the inform time decreases directly with the edge size . [Copyright &y& Elsevier]