Clairvoyant embedding in one dimension. Issue 3 (13th June 2014) - Gács, Peter
Abstract Let v, w be infinite 0‐1 sequences, and m˜ a positive integer. We say that w is m˜‐embeddable in v, if there exists an increasing sequence (ni:i≥0) of integers with n0=0, such that 1≤ni−ni−1≤m˜, w(i)=v(ni) for all i≥1. Let X and Y be coin‐tossing sequences. We will show that there is an m˜ with the property that Y is m˜‐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