Mathematics – Probability
Scientific paper
2012-04-14
Mathematics
Probability
32 pages, 5 figures
Scientific paper
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^\prime$ and $p$ respectively, does it 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^\prime$ very close to 1/2. In the positive direction, we construct, for any $\epsilon > 0$, a deterministic binary sequence $\eta_\epsilon$ whose set of zeroes has Hausdorff dimension larger than $1-\epsilon$, and such that $\mathbb{P}_p {\xi\colon (\eta_\epsilon,\xi) \text {is compatible}} > 0$ for $p$ small enough, where $\mathbb{P}_p$ stands for the product Bernoulli measure with parameter $p$.
de Lima Bernardo N. B.
Kesten Harry
Sidoravicius Vladas
Vares Maria Eulalia
No associations
LandOfFree
On the compatibility of binary sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the compatibility of binary sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the compatibility of binary sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-33616