We consider the problem of embedding one i.i.d. collection of Bernoulli random variables indexed by @math into an independent copy in an injective @math -Lipschitz manner. For the case @math , it was shown by Basu and Sly (PTRF, 2014) to be possible almost surely for sufficiently large @math . In this paper we provide a multi-scale argument extending this result to higher dimensions.
 For a natural number k, define an oriented site percolation on ℤ2 as follows. Let x i , y j be independent random variables with values uniformly distributed in 1, …, k . Declare a site (i, j) ∈ℤ2closed if x i = y j , and open otherwise. Peter Winkler conjectured some years ago that if k≥ 4 then with positive probability there is an infinite oriented path starting at the origin, all of whose sites are open. I.e., there is an infinite path P = (i0, j0)(i1, j1) · · · such that 0 = i0≤i1≤· · ·, 0 = j0≤j1≤· · ·, and each site (i n , j n ) is open. Rather surprisingly, this conjecture is still open: in fact, it is not known whether the conjecture holds for any value of k. In this note, we shall prove the weaker result that the corresponding assertion holds in the unoriented case: if k≤ 4 then the probability that there is an infinite path that starts at the origin and consists only of open sites is positive. Furthermore, we shall show that our method can be applied to a wide variety of distributions of (x i ) and (y j ). Independently, Peter Winkler [14] has recently proved a variety of similar assertions by different methods. Let v, w be infinite 0-1 sequences, and mi¾? a positive integer. We say that w is mi¾?-embeddable in v, if there exists an increasing sequence ni:ii¾?0 of integers with n0=0, such that 1i¾?ni-ni-1i¾?mi¾?, wi=vni for all ii¾?1. Let X and Y be coin-tossing sequences. We will show that there is an mi¾? with the property that Y is mi¾?-embeddable into X with positive probability. This answers a question that was open for a while. The proof generalizes somewhat the hierarchical method of an earlier paper of the author on dependent percolation. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 520-560, 2015 We consider a type of long-range percolation problem on the positive integers, motivated by earlier work of others on the appearance of (in)finite words within a site percolation model. The main issue is whether a given infinite binary word appears within an iid Bernoulli sequence at locations that satisfy certain constraints. We settle the issue in some cases, and we provide partial results in others. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 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. A number of tricky problems in probability are discussed, having in common one or more infinite sequences of coin tosses, and a representation as a problem in dependent percolation. Three of these problems are of Winkler' type, that is, they ask about what can be achieved by a clairvoyant demon. A token located at some vertex @math of a connected, undirected graph G on n vertices is said to be taking a “random walk” on G if, whenever it is instructed to move, it moves with equal probability to any of the neighbors of @math . The authors consider the following problem: Suppose that two tokens are placed on G, and at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying to keep the tokens apart as long as possible. What is the expected time M before they meet?The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing. Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound. The authors use a novel potential function argument to show that in the worst case @math .