On the Compatibility of Binary Sequences

DOI10.1002/CPA.21486MaRDI QIDQ5418793zbMATH OpenOpenAlexFDO

Authors Harry Kesten, Bernardo Nunes Borges de Lima, Vladas Sidoravicius, Maria Eulalia Vares

Publication date 28 May 2014

Published in Communications on Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.3197

zbMATH Keywords

binary sequencespercolationcompatibility

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: An ordered pair of semi-infinite binary sequences $(eta,xi)$ is said to be compatible if there is a way of removing a certain number (possibly infinite) of ones from $eta$ and zeroes from $xi$, whichwould map both sequences to the same semi-infinite sequence. This notion was introduced by Peter Winkler, who also posed the following question: $eta$ and $xi$ being independent i.i.d. Bernoulli sequences with parameters $p^{p}rime$ and $p$ respectively, does it exist $(p^{\prime },p)$ so that the set of compatible pairs has positive measure? It is known that this does not happen for $p$ and $p^{p}rime$ very close to 1/2. In the positive direction, we construct, for any $epsilon>0$, a deterministic binary sequence $et{a}_{e}psilon$ whose set of zeroes has Hausdorff dimension larger than $1-epsilon$, and such that $mathbb{P}_{p}xicolon(et{a}_{e}psilon,xi)extiscompatible>0$ for $p$ small enough, where $mathbb{P}_p$ stands for the product Bernoulli measure with parameter $p$.

Recommendations

• scientific article; zbMATH DE number 2154139
• On a Class of Binary Sequences
• On the existence of periodic complementary binary sequences
• scientific article; zbMATH DE number 5150220
• On aperiodic and periodic complementary binary sequences
• Equivalence Systems on Sets of Binary Sequences
• scientific article; zbMATH DE number 1123791
• On binary recurrence sequences
• On random binary sequences
• On Jacobsthal binary sequences

Cites work

• scientific article; zbMATH DE number 1496578 (Why is no real title available?)
• scientific article; zbMATH DE number 1416163 (Why is no real title available?)
• scientific article; zbMATH DE number 3205162 (Why is no real title available?)
• Compatible Sequences and a Slow Winkler Percolation
• Defining Fractal Subsets of Z ^d
• Dimensions of fractals in the large
• Lipschitz embeddings of random sequences
• Percolation of arbitrary words in \(\{0, 1\}^ \mathbb{N}\)
• Percolation of arbitrary words in one dimension

Cited in

(8)

• Dependent percolation on \(\mathbb{Z}^2\)
• Lipschitz embeddings of random sequences
• Oriented percolation in a random environment
• Compatible sequences and a slow Winkler percolation
• Embedding binary sequences into Bernoulli site percolation on \(\mathbb{Z}^3\)
• Discrete fractals: dimensions, quasi-isometric invariance and self-similarity
• Scheduling of non-colliding random walks
• Sequences of binary strings with relation of conditional simplicity

This page was built for publication: On the Compatibility of Binary Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5418793)