, X(t) and X (t) can be coupled (in a natural way), so that they both hit a vertex in V at the same round. Let h = 12 · ? R and ? 2 = ? 2 h k+1 log for some constant ? 2 > 0. By symmetry of V , we can assume that one of the coordinates of x is less than h/2, w.l.o.g., 0 ? x 1 < h/2. Consider a walk Y (t) on a smaller k-dimensional torus H with h vertices on each side, where each coordinate of Y (t) is the same as that coordinate of X (t), modulo h. By [29, Sec. 11.3.2], the expected cover time of Y is at most O(kh k log h) = O(h k+1 ), therefore, for a sufficiently large ? 2 , the walk Y visits all vertices of H in ? 2 rounds, with probability at least 1 ? n ?? /2. Let z be the vertex of H with all its coordinates equal to h/2 = 6? R . If Y (t) = z and t < l ? h, then X (t) ? V , because no vertex in V \ V has its first coordinate equal to h/2 (modulo h) and is less than l ? h steps away from x. It implies that in ? 2 rounds X (t) (and thus, X(t)) visits some vertex in V, Next, our goal is to bound the number of rounds until X(t) reaches one of the vertices in V after round ? x . Consider a random walk X (t) on a k-dimensional torus with vertices on each side, for which too we use V to denote the set of its "central" vertices. Since V is equidistant from the sides of the grid G
Reversible markov chains and random walks on graphs, 2002. ,
Random walks, universal traversal sequences, and the complexity of maze problems, Proc. 20th IEEE Symposium on Foundations of Computer Science, FOCS, pp.218-223, 1979. ,
Many random walks are faster than one, Combinatorics, Probability & Computing, vol.20, issue.4, pp.481-502, 2011. ,
The shape theorem for the frog model, The Annals of Applied Probability, vol.12, issue.2, pp.533-546, 2002. ,
, Balanced allocations. SIAM J. Comput, vol.29, issue.1, pp.180-200, 1999.
Trading space for time in undirected s-t connectivity, SIAM J. Comput, vol.23, issue.2, pp.324-334, 1994. ,
Rumor spreading and conductance, J. ACM, vol.65, issue.4, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01942162
Concentration inequalities and martingale inequalities: A survey, Internet Mathematics, vol.3, issue.1, pp.79-127, 2006. ,
Random walks, interacting particles, dynamic networks: Randomness can be helpful, Proc. 18th International Colloquium on Structural Information and Communication Complexity, SIROCCO, pp.1-14, 2011. ,
Multiple random walks in random regular graphs, SIAM J. Discrete Math, vol.23, issue.4, pp.1738-1761, 2009. ,
Epidemic algorithms for replicated database maintenance, Operating Systems Review, vol.22, issue.1, pp.8-32, 1988. ,
The infection time of graphs, Discrete Applied Mathematics, vol.154, issue.18, pp.2577-2589, 2006. ,
Social networks spread rumors in sublogarithmic time, Proc. 43rd ACM Symposium on Theory of Computing, STOC, pp.21-30, 2011. ,
Concentration of Measure for the Analysis of Randomized Algorithms, 2009. ,
How well do random walks parallelize?, Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp.476-489, 2009. ,
Tight bounds for the cover time of multiple random walks, Theor. Comput. Sci, vol.412, issue.24, pp.2623-2641, 2011. ,
Randomized broadcast in networks, Random Struct. Algorithms, vol.1, issue.4, pp.447-460, 1990. ,
Wiley series in probability and mathematical statistics, An Introduction to Probability Theory and its Applications, vol.1, 1968. ,
How to spread a rumor: Call your neighbors or take a walk?, Proc. 38th ACM Symposium on Principles of Distributed Computing, PODC, pp.24-33, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-02388328
How to spread a rumor: Call your neighbors or take a walk? CoRR, abs, 2006. ,
Percolation of lipschitz surface and tight bounds on the spread of information among mobile agents, Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, vol.116, pp.1-39, 2018. ,
Frogs on trees? Electron, J. Probab, vol.23, p.40, 2018. ,
Randomized rumor spreading, Proc. 41st IEEE Symposium on Foundations of Computer Science, FOCS, pp.565-574, 2000. ,
Branching random walk with catalysts. Electronic Journal of Probability, vol.8, 2003. ,
The spread of a rumor or infection in a moving population, The Annals of Probability, vol.33, issue.6, pp.2402-2462, 2005. ,
A shape theorem for the spread of an infection, Annals of Mathematics, vol.167, issue.3, pp.701-766, 2008. ,
How long do nosocomial pathogens persist on inanimate surfaces? A systematic review, BMC Infectious Diseases, vol.6, issue.1, p.130, 2006. ,
Information dissemination via random walks in d-dimensional space, Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.1612-1622, 2012. ,
Markov Chains and Mixing Times, 2017. ,
Sharp bounds on random walk eigenvalues via spectral embedding, International Mathematics Research Notices, issue.24, pp.7555-7605, 2017. ,
Random walks on graphs: New bounds on hitting, meeting, coalescing and returning, Proc. 16th Workshop on Analytic Algorithmics and Combinatorics, ANALCO, pp.119-126, 2019. ,
Infectious random walks. CoRR, 2010. ,
Tight bounds on information dissemination in sparse mobile networks, Proc. 30th ACM Symposium on Principles of Distributed Computing, PODC, pp.355-362, 2011. ,
Frogs and some other interacting random walks models, Proc. Discrete Random Walks, DRW, pp.277-288, 2003. ,