, 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

D. Aldous and J. A. Fill, Reversible markov chains and random walks on graphs, 2002.

R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff, 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.

N. Alon, C. Avin, M. Koucký, G. Kozma, Z. Lotker et al., Many random walks are faster than one, Combinatorics, Probability & Computing, vol.20, issue.4, pp.481-502, 2011.

O. S. Alves, F. P. Machado, S. Yu, and . Popov, The shape theorem for the frog model, The Annals of Applied Probability, vol.12, issue.2, pp.533-546, 2002.

Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, Balanced allocations. SIAM J. Comput, vol.29, issue.1, pp.180-200, 1999.

A. Z. Broder, A. R. Karlin, P. Raghavan, and E. Upfal, Trading space for time in undirected s-t connectivity, SIAM J. Comput, vol.23, issue.2, pp.324-334, 1994.

F. Chierichetti, G. Giakkoupis, S. Lattanzi, and A. Panconesi, Rumor spreading and conductance, J. ACM, vol.65, issue.4, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01942162

R. K. Fan, L. Chung, and . Lu, Concentration inequalities and martingale inequalities: A survey, Internet Mathematics, vol.3, issue.1, pp.79-127, 2006.

C. Cooper, 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.

C. Cooper, A. M. Frieze, and T. Radzik, Multiple random walks in random regular graphs, SIAM J. Discrete Math, vol.23, issue.4, pp.1738-1761, 2009.

A. J. Demers, D. H. Greene, C. Hauser, W. Irish, J. Larson et al., Epidemic algorithms for replicated database maintenance, Operating Systems Review, vol.22, issue.1, pp.8-32, 1988.

T. Dimitriou, S. E. Nikoletseas, and P. G. Spirakis, The infection time of graphs, Discrete Applied Mathematics, vol.154, issue.18, pp.2577-2589, 2006.

B. Doerr, M. Fouz, and T. Friedrich, Social networks spread rumors in sublogarithmic time, Proc. 43rd ACM Symposium on Theory of Computing, STOC, pp.21-30, 2011.

P. Devdatt, A. Dubhashi, and . Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, 2009.

K. Efremenko and O. Reingold, How well do random walks parallelize?, Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp.476-489, 2009.

R. Elsässer and T. Sauerwald, Tight bounds for the cover time of multiple random walks, Theor. Comput. Sci, vol.412, issue.24, pp.2623-2641, 2011.

U. Feige, D. Peleg, P. Raghavan, and E. Upfal, Randomized broadcast in networks, Random Struct. Algorithms, vol.1, issue.4, pp.447-460, 1990.

W. Feller, Wiley series in probability and mathematical statistics, An Introduction to Probability Theory and its Applications, vol.1, 1968.

G. Giakkoupis, F. Mallmann-trenn, and H. Saribekyan, 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

G. Giakkoupis, F. Mallmann-trenn, and H. Saribekyan, How to spread a rumor: Call your neighbors or take a walk? CoRR, abs, 2006.

P. Gracar and A. Stauffer, 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.

J. Hermon, Frogs on trees? Electron, J. Probab, vol.23, p.40, 2018.

R. M. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking, Randomized rumor spreading, Proc. 41st IEEE Symposium on Foundations of Computer Science, FOCS, pp.565-574, 2000.

H. Kesten and V. Sidoravicius, Branching random walk with catalysts. Electronic Journal of Probability, vol.8, 2003.

H. Kesten and V. Sidoravicius, The spread of a rumor or infection in a moving population, The Annals of Probability, vol.33, issue.6, pp.2402-2462, 2005.

H. Kesten and V. Sidoravicius, A shape theorem for the spread of an infection, Annals of Mathematics, vol.167, issue.3, pp.701-766, 2008.

A. Kramer, I. Schwebke, and G. Kampf, How long do nosocomial pathogens persist on inanimate surfaces? A systematic review, BMC Infectious Diseases, vol.6, issue.1, p.130, 2006.

H. Lam, Z. Liu, M. Mitzenmacher, X. Sun, and Y. Wang, Information dissemination via random walks in d-dimensional space, Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, SODA, pp.1612-1622, 2012.

D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing Times, 2017.

R. Lyons and . Shayan-oveis-gharan, Sharp bounds on random walk eigenvalues via spectral embedding, International Mathematics Research Notices, issue.24, pp.7555-7605, 2017.

R. I. Oliveira and Y. Peres, 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.

A. Pettarin, A. Pietracaprina, G. Pucci, and E. Upfal, Infectious random walks. CoRR, 2010.

A. Pettarin, A. Pietracaprina, G. Pucci, and E. Upfal, Tight bounds on information dissemination in sparse mobile networks, Proc. 30th ACM Symposium on Principles of Distributed Computing, PODC, pp.355-362, 2011.

S. Yu and . Popov, Frogs and some other interacting random walks models, Proc. Discrete Random Walks, DRW, pp.277-288, 2003.