On the Compatibility of Binary Sequences

An ordered pair of semi‐infinite binary sequences (η,ξ) is said to be compatible if there is a way of removing a certain number (possibly infinite) of ones from η and zeroes from ξ that would map both sequences to the same semi‐infinite sequence. This notion was introduced by Peter Winkler, who also posed the following question: η and ξ being independent i.i.d. Bernoulli sequences with parameters p ′ and p , respectively, does there exist ( p ′, p ) so that the set of compatible pairs has positive measure? It is known that this does not happen for p and p ′ very close to1 2 . In the positive direction, we construct, for any ɛ > 0, a deterministic binary sequence η ɛ whose set of zeroes has Hausdorff dimension larger than 1 − ɛ and such that ℙ p {ξ : (η ɛ ,ξ) is compatible } > 0 for p small enough, where ℙ p stands for the product Bernoulli measure with parameter p . © 2014 Wiley Periodicals, Inc.