Scheduling of Non-Colliding Random Walks

Riddhipratim Basu, Vladas Sidoravicius, Allan Sly

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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].

Original languageEnglish (US)
Title of host publicationSojourns in Probability Theory and Statistical Physics - III - Interacting Particle Systems and Random Walks, A Festschrift for Charles M. Newman
EditorsVladas Sidoravicius
PublisherSpringer
Pages90-137
Number of pages48
ISBN (Print)9789811503016
DOIs
StatePublished - 2019
EventInternational Conference on Probability Theory and Statistical Physics, 2016 - Shanghai, China
Duration: Mar 25 2016Mar 27 2016

Publication series

NameSpringer Proceedings in Mathematics and Statistics
Volume300
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017

Conference

ConferenceInternational Conference on Probability Theory and Statistical Physics, 2016
CountryChina
CityShanghai
Period3/25/163/27/16

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Dependent percolation
  • Renormalization

Fingerprint Dive into the research topics of 'Scheduling of Non-Colliding Random Walks'. Together they form a unique fingerprint.

  • Cite this

    Basu, R., Sidoravicius, V., & Sly, A. (2019). Scheduling of Non-Colliding Random Walks. In V. Sidoravicius (Ed.), Sojourns in Probability Theory and Statistical Physics - III - Interacting Particle Systems and Random Walks, A Festschrift for Charles M. Newman (pp. 90-137). (Springer Proceedings in Mathematics and Statistics; Vol. 300). Springer. https://doi.org/10.1007/978-981-15-0302-3_4