Scheduling of non-colliding random walks

DOI10.1007/978-981-15-0302-3_4MaRDI QIDQ3297346zbMATH OpenOpenAlexFDO

Authors Riddhipratim Basu, Allan Sly, Vladas Sidoravicius

Publication date 3 July 2020

Published in Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.4041

zbMATH Keywords

dependent percolationrenormalization

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Boundary theory for Markov processes (60J50) Jump processes on discrete state spaces (60J74) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Renormalization group methods in equilibrium statistical mechanics (82B28) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Percolation (82B43)

Abstract: On the complete graph ${calK}_M$ with $Mge3$ vertices consider two independent discrete time random walks $mathbbX$ and $mathbbY$, choosing their steps uniformly at random. A pair of trajectories $mathbbX=X_1,X_2,dots$ and $mathbbY=Y_1,Y_2,dots$ is called {it{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 $mathbbX,mathbbY$ 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.

Recommendations

• Clairvoyant scheduling of random walks
• Avoidance coupling
• scientific article; zbMATH DE number 1416163
• Compatible Sequences and a Slow Winkler Percolation

Cites work

• Avoidance coupling
• Clairvoyant embedding in one dimension
• Clairvoyant scheduling of random walks
• Collisions Among Random Walks on a Graph
• Compatible Sequences and a Slow Winkler Percolation
• Corner percolation on \(\mathbb Z^{2}\) and the square root of 17
• Dependent percolation in two dimensions
• scientific article; zbMATH DE number 1416163 (Why is no real title available?)
• Lipschitz embeddings of random sequences
• On a Form of Coordinate Percolation
• On rough isometries of Poisson processes on the line
• On the Compatibility of Binary Sequences
• On the statistics of vision: The Julesz conjecture
• Percolation of arbitrary words in one dimension
• Submodular percolation
• The clairvoyant demon has a hard task
• Three problems for the clairvoyant demon
• Vacant set of random interlacements and percolation

Cited in

(7)

• Oriented percolation in a random environment
• scientific article; zbMATH DE number 1416163 (Why is no real title available?)
• An upper bound on the size of avoidance couplings
• Clairvoyant scheduling of random walks
• Evolutionary Computation in Combinatorial Optimization
• Avoidance couplings on non‐complete graphs
• Percolation on stretched lattices: a static renormalization approach

This page was built for publication: Scheduling of non-colliding random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297346)