We study the dynamics of information (or virus) dissemination by @math mobile agents performing independent random walks on an @math -node grid. We formulate our results in terms of two scenarios: broadcasting and gossiping. In the broadcasting scenario, the mobile agents are initially placed uniformly at random among the grid nodes. At time 0, one agent is informed of a rumor and starts a random walk. When an informed agent meets an uninformed agent, the latter becomes informed and starts a new random walk. We study the broadcasting time of the system, that is, the time it takes for all agents to know the rumor. In the gossiping scenario, each agent is given a distinct rumor at time 0 and all agents start random walks. When two agents meet, they share all rumors they are aware of. We study the gossiping time of the system, that is, the time it takes for all agents to know all rumors. We prove that both the broadcasting and the gossiping times are @math w.h.p., thus achieving a tight characterization up to logarithmic factors. Previous results for the grid provided bounds which were weaker and only concerned average times. In the context of virus infection, a corollary of our results is that static and dynamically moving agents are infected at about the same speed.
Finally, a related line of research deals with the cover time of a random walk on a graph, that is, the expected time when all of the graph nodes are touched by the random walk. (See @cite_14 for a comprehensive account of the relevant literature.) The cover time is strictly related to the hitting time @cite_6 , namely the average time required of a random walk to reach a specified node. For @math -node meshes, it is known that the hitting time is @math , while the cover time is @math @cite_8 @cite_3 . Bounds on the speed-up achieved on the cover time by multiple random walks as opposed to a single one are proved in @cite_4 @cite_5 .
@cite_14 @cite_4 @cite_8 @cite_3 @cite_6 @cite_5
2160504298 2138144746 2048572907 2094887806 1564693713
We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probablistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds. A general technique for proving lower bounds on expected covering times of random walks on graphs in terms of expected hitting times between vertices is given. This technique is used to prove (i) A tight bound of @math for the two-dimensional torus; (ii) A tight bound of @math for trees with maximum degree @math ; (iii) Tight bounds of @math for rapidly mixing walks on vertex transitive graphs, where @math denotes the maximum expected hitting time between vertices.In addition to these new results, the technique allows several known lower bounds on cover times to be systematically proved, often in a much simpler way.Finally, a different technique is used to prove an @math lower bound on the cover time, where @math is the second largest eigenvalue of the transition matrix. This was previously known only in the case where the walk starts in the stationary distribution [... [20th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1979, pp. 218--223] posed the following question: "The reachability problem for undirected graphs can be solved in log space and @math time [ @math is the number of edges and @math is the number of vertices] by a probabilistic algorithm that simulates a random walk, or in linear time and space by a conventional deterministic graph traversal algorithm. Is there a spectrum of time-space trade-offs between these extremes?" This question is answered in the affirmative for sparse graphs by presentation of an algorithm that is faster than the random walk by a factor essentially proportional to the size of its workspace. For denser graphs, this algorithm is faster than the random walk but the speed-up factor is smaller. We study the cover time of multiple random walks. Given a graph G of n vertices, assume that k independent random walks start from the same vertex. The parameter of interest is the speed-up defined as the ratio between the cover time of one and the cover time of k random walks. Recently developed several bounds that are based on the quotient between the cover time and maximum hitting times. Their technique gives a speed-up of *** (k ) on many graphs, however, for many graph classes, k has to be bounded by @math . They also conjectured that, for any 1 ≤ k ≤ n , the speed-up is at most @math on any graph. As our main results, we prove the following: We present a new lower bound on the speed-up that depends on the mixing-time. It gives a speed-up of *** (k ) on many graphs, even if k is as large as n . We prove that the speed-up is @math on any graph. Under rather mild conditions, we can also improve this bound to @math , matching exactly the conjecture of We find the correct order of the speed-up for any value of 1 ≤ k ≤ n on hypercubes, random graphs and expanders. For d -dimensional torus graphs (d > 2), our bounds are tight up to a factor of @math . Our findings also reveal a surprisingly sharp dichotomy on several graphs (including d -dim. torus and hypercubes): up to a certain threshold the speed-up is k , while there is no additional speed-up above the threshold.