Search

In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues a random walk through the graph. Let G =(V, E) bean undirected and connected graph with n vertices and m edges. The coalescence time, C(n), is the expected time for all particles to coalesce, when initially one particle is located at each vertex. We study the problem of bounding the coalescence time for general connected graphs and prove that C(n)= O(1/1-λ2(log4 n+n/v)). Here λ2 is the second eigenvalue of the transition matrix of the random walk. To avoid problems arising from, e.g., lack of coalescence on bipartite graphs, we assume the random walk can be made lazy if required. The value of v is given by ..., where d(v) is the degree of vertex v,and d = 2m/n is the average degree. The parameter v is an indicator of the variability of vertex degrees: 1 ≤ v = O(n), with v = 1 for regular graphs. Our general bound on C(n) holds for all connected graphs. This implies, for example, that C(n)= O(n/(1 - λ2)) for d-regular graphs with expansion parameterized by the eigenvalue gap 1 - λ2. The bound on C(n) given above is sublinear for some classes of graphs with skewed degree distributions. In the voter model, initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. Let E(Cv) be the expected time for voting to complete, that is, for a unique opinion to emerge. A system of coalescing particles, where initially one particle is located at each vertex, corresponds to the voter model in that E(Cv)= C(n). Thus our result stated above for C(n) also gives general bounds for E(Cv). [ABSTRACT FROM AUTHOR]

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]