TY - GEN
T1 - Scheduling of Non-Colliding Random Walks
AU - Basu, Riddhipratim
AU - Sidoravicius, Vladas
AU - Sly, Allan
N1 - Funding Information:
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.
Publisher Copyright:
© Springer Nature Singapore Pte Ltd. 2019.
PY - 2019
Y1 - 2019
N2 - On the complete graph KM with M ≥ 3 vertices consider two independent discrete time random walks X and Y, choosing their steps uniformly at random. A pair of trajectories X = {X1, X2, ...} and Y = {Y1, Y2, ...} 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 {X, 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].
AB - On the complete graph KM with M ≥ 3 vertices consider two independent discrete time random walks X and Y, choosing their steps uniformly at random. A pair of trajectories X = {X1, X2, ...} and Y = {Y1, Y2, ...} 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 {X, 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].
KW - Dependent percolation
KW - Renormalization
UR - http://www.scopus.com/inward/record.url?scp=85085735663&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85085735663&partnerID=8YFLogxK
U2 - 10.1007/978-981-15-0302-3_4
DO - 10.1007/978-981-15-0302-3_4
M3 - Conference contribution
AN - SCOPUS:85085735663
SN - 9789811503016
T3 - Springer Proceedings in Mathematics and Statistics
SP - 90
EP - 137
BT - Sojourns in Probability Theory and Statistical Physics - III - Interacting Particle Systems and Random Walks, A Festschrift for Charles M. Newman
A2 - Sidoravicius, Vladas
PB - Springer
T2 - International Conference on Probability Theory and Statistical Physics, 2016
Y2 - 25 March 2016 through 27 March 2016
ER -