On the complete graph @math with @math vertices consider two independent discrete time random walks @math and @math , choosing their steps uniformly at random. A pair of trajectories @math and @math 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 @math the set of pairs of non-colliding trajectories @math 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 @math . In this paper we establish the conjecture.
@cite_12: Two infinite walks on the same finite graph are called compatible if it is possible to introduce delays into them in such a way that they never collide. Years ago, Peter Winkler asked the question: for which graphs are two independent random walks compatible with positive probability. Up to now, no such graphs were found. We show in this paper that large complete graphs have this property. The question is equivalent to a certain dependent percolation with a power-law behavior: the probability that the origin is blocked at distance n but not closer decreases only polynomially fast and not, as usual, exponentially. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 © 2011 Wiley Periodicals, Inc.
@cite_17: We develop a new multi-scale framework flexible enough to solve a number of problems involving embedding random sequences into random sequences. (Random Str Algorithm 37(1):85–99, 2010) asked whether there exists an increasing (M )-Lipschitz embedding from one i.i.d. Bernoulli sequence into an independent copy with positive probability. We give a positive answer for large enough (M ). A closely related problem is to show that two independent Poisson processes on ( R ) are roughly isometric (or quasi-isometric). Our approach also applies in this case answering a conjecture of Szegedy and of Peled (Ann Appl Probab 20:462–494, 2010). Our theorem also gives a new proof to Winkler’s compatible sequences problem. Our approach does not explicitly depend on the particular geometry of the problems and we believe it will be applicable to a range of multi-scale and random embedding problems.
In @cite_17 a multi-scale structure was developed to tackle random embedding problems which can be recast in co-ordinate percolation framework. As a corollary of a general embedding theorem, it was proved there that an i.i.d. Bernoulli sequence can almost surely be embedded into another in a Lipschitz manner provided that the Lipschitz constant is sufficiently large. It also led to a proof of rough isometry of two one-dimensional Poisson processes as well as a new proof of Winkler's compatible sequence problem. In this work we build upon the methods of @cite_17 , using a similar multi-scale structure, but with crucial adaptations. An earlier proof of Theorem 1 appeared in @cite_12 with a very difficult multi-scale argument. Our proof is different and we believe gives a clearer inductive structure. We also believe that our proof can be adapted to deal with this problem on several other graphs, as well as in the case where there are multiple random walks.