Scheduling of Non-Colliding Random Walks

• Riddhipratim Basu
• Allan Sly
Conference paper
Part of the Springer Proceedings in Mathematics & Statistics book series (PROMS, volume 300)

Abstract

On the complete graph $$\mathcal{{K}}_M$$ with $$M \ge 3$$ vertices consider two independent discrete time random walks $$\mathbb {X}$$ and $$\mathbb {Y}$$, choosing their steps uniformly at random. A pair of trajectories $$\mathbb {X} = \{ X_1, X_2, \dots \}$$ and $$\mathbb {Y} = \{Y_1, Y_2, \dots \}$$ is called non-colliding, if by delaying their jump times one can keep both walks at distinct vertices forever. It was conjectured by P. Winkler that for large enough M the set of pairs of non-colliding trajectories $$\{\mathbb {X},\mathbb {Y} \}$$ has positive measure. N. Alon translated this problem to the language of coordinate percolation, a class of dependent percolation models, which in most situations is not tractable by methods of Bernoulli percolation. In this representation Winkler’s conjecture is equivalent to the existence of an infinite open cluster for large enough M. In this paper we establish the conjecture building upon the renormalization techniques developed in [4].

Keywords

Dependent percolation Renormalization

Notes

Acknowledgements

This work was completed when R.B. was a graduate student at the Department of Statistics at UC Berkeley and the result in this paper appeared in Chap. 3 of his Ph.D. dissertation at UC Berkeley: Lipschitz Embeddings of Random Objects and Related Topics, 2015. During the completion of this work R. B. was supported by UC Berkeley graduate fellowship, V. S. was supported by CNPq grant Bolsa de Produtividade, and A.S. was supported by NSF grant DMS–1352013. R.B. is currently supported by an ICTS-Simons Junior Faculty Fellowship and a Ramanujan Fellowship from Govt. of India and A.S. is supported by a Simons Investigator grant.

References

1. 1.
Abete, T., de Candia, A., Lairez, D., Coniglio, A.: Percolation model for enzyme gel degradation. Phys. Rev. Letters 93, 228301 (2004)
2. 2.
Omer, A., Holroyd, A., Martin, J., Winkler, P., Wilson, D.: Avoidance coupling. Electron. Commun. Probab. 18, 1–13 (2013)
3. 3.
Balister, P.N., Bollobás, B., Stacey, A.M.: Dependent percolation in two dimensions. Probab. Theory Related Fields 117, 495–513 (2000)
4. 4.
Basu, R., Sly, A.: Lipschitz embeddings of random sequences. Prob. Th. Rel. Fields 159(3–4), 721–775 (2014)
5. 5.
Brightwell, G.R., Winkler, P.: Submodular percolation. SIAM J. Discret. Math. 23(3), 1149–1178 (2009)
6. 6.
Coppersmith, D., Tetali, P., Winkler, P.: Collisions among random walks on a graph. SIAM J. Discrete Math. 6, 363–374 (1993)
7. 7.
Diaconis, P., Freedman, D.: On the statistics of vision: the Julesz conjecture. J. Math. Psychol. 24(2), 112–138 (1981)
8. 8.
Gács, P.: The clairvoyant demon has a hard task. Comb. Probab. Comput. 9(5), 421–424 (2000)
9. 9.
Gács, P.: Compatible sequences and a slow Winkler percolation. Combin. Probab. Comput. 13(6), 815–856 (2004)
10. 10.
Gács, P.: Clairvoyant scheduling of random walks. Random Struct. Algorithms 39, 413–485 (2011)
11. 11.
Gács, P.: Clairvoyant embedding in one dimension. Random Struct. Alg. 47, 520–560 (2015)
12. 12.
Grimmett, G.: Three problems for the clairvoyant demon. Preprint arXiv:0903.4749 (2009)
13. 13.
Grimmett, G.R., Liggett, T.M., Richthammer, T.: Percolation of arbitrary words in one dimension. Random Struct. Algorithms 37(1), 85–99 (2010)
14. 14.
Kesten, H., de Lima, B., Sidoravicius, V., Vares, M.E.: On the compatibility of binary sequences. Comm. Pure Appl. Math. 67(6), 871–905 (2014)
15. 15.
Moseman, E., Winkler, P.: On a form of coordinate percolation. Comb. Probab. Comput. 17, 837–845 (2008)
16. 16.
Peled, R.: On rough isometries of Poisson processes on the line. Ann. Appl. Probab. 20, 462–494 (2010)
17. 17.
Pete, G.: Corner percolation on $$\mathbb{Z}^2$$ and the square root of 17. Ann. Probab. 36(5), 1711–1747 (2008)Google Scholar
18. 18.
Rolla, L., Werner, W.: Percolation of Brownian loops in three dimensions (in preparation)Google Scholar
19. 19.
Symanzik, K.: Euclidean quantum field theory. In: Jost, R. (ed.) Local Quantum Theory. Academic Press, Cambridge (1969)Google Scholar
20. 20.
Sznitman, A.-S.: Vacant set of random interlacement and percolation. Ann. Math. 171(3), 2039–2087 (2010)
21. 21.
Winkler, P.: Dependent percolation and colliding random walks. Rand. Struct. Alg. 16(1), 58–84 (2000)

© Springer Nature Singapore Pte Ltd. 2019

Authors and Affiliations

• Riddhipratim Basu
• 1
Email author