Premium
On the Compatibility of Binary Sequences
Author(s) -
Kesten Harry,
Lima Bernardo N. B.,
Sidoravicius Vladas,
Vares Maria Eulália
Publication year - 2014
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.21486
Subject(s) - mathematics , bernoulli's principle , binary number , combinatorics , hausdorff dimension , sequence (biology) , measure (data warehouse) , set (abstract data type) , pseudorandom binary sequence , product (mathematics) , discrete mathematics , compatibility (geochemistry) , arithmetic , geometry , physics , thermodynamics , genetics , geochemistry , database , biology , computer science , programming language , geology
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.