30
$\begingroup$

Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, $0<c<1$). Is the following always true?

A random infinite word $a_1a_2\dots$ may be partitioned onto words from $M$ with probability at least $c$?

Actually, I am not sure even that such a probability does necessary exist, so strictly speaking what I am asking is a ``lower measure at least $c$''.

$\endgroup$
  • 6
    $\begingroup$ The set of infinite words that are partitionable into words from $M$ is an analytic set (i.e., a continuous image of a Borel set), so it is measurable. $\endgroup$ – Andreas Blass Apr 30 '14 at 14:18
  • $\begingroup$ If M is finite how does it contain c2^n words of length n for all large enough n? Or do you mean the submonoid generated by M contains at least density c for all large enough n? $\endgroup$ – Benjamin Steinberg Apr 30 '14 at 15:36
  • 2
    $\begingroup$ The words are finite: M is not. Also the density condition means there is no finite word avoided by M. The conjecture seems plausible, especially when M consists of all words with the same prefix. $\endgroup$ – The Masked Avenger Apr 30 '14 at 16:13
  • $\begingroup$ @TheMaskedAvenger, thanks. I misread the question as a finite set of words on my little phone. $\endgroup$ – Benjamin Steinberg Apr 30 '14 at 18:45
9
$\begingroup$

OK, let's try. If I haven't made any mistake, this is just a standard "condition on the head-cut the tail" measure theory puzzle.

Claim 1. The condition $A_1$ that the sequence contains an arbitrarily long word from $M$ starting from the beginning is a Borel event of probability $\ge c$.

Proof: $A_1=\cap_{n\ge 1}\cup_{m\ge n}M_m\times\{0,1\}^\omega$ and the unions are nested and all have probability $\ge c$.

Claim 2. For every $\varepsilon>0$, there exists $n(\varepsilon)$ and a subset $M(\varepsilon)$ of strings of length $n(\varepsilon)$ of relative size $\ge c-2\varepsilon$ such that for every string $x\in M(\varepsilon)$ the probability that a random string starting with $x$ is in $A_1$ is at least $1-\varepsilon$.

Proof: Just take any cylinder event $B_1=M'\times \{0,1\}^\omega$ such that $P(A_1\Delta B_1)\le \varepsilon^2$ and remove the strings $x\in M'$ for which the conditional probability of failing to be in $A_1$ under the assumption that the string starts with $x$ is at least $\varepsilon$.

Claim 3. Let $\delta>0$. Then for every $x\in M(\varepsilon)$ the probability that the random string starting with $x$ contains a string from $M$ (starting from the beginning) followed by a string from $M(\delta)$ is at least $1-3c^{-1}\varepsilon$.

Proof: Condition everything upon the beginning $x$. Let $A_2$ be the (obviously, Borel) event that no string in $M$ is followed by a string from $M(\delta)$. Let $B_2$ be a cylinder event depending on the first $n$ entries such that $P(A_2\Delta B_2)\le \varepsilon$. Then $$ P(A_2)\le 2\varepsilon+P(B_2\cap A_2\cap A_1)\le 2\varepsilon+P(B_2)(1-c)\le 3\varepsilon+P(A_2)(1-c) $$ because once we are in $B_2\cap A_1$, we are in $B_2$ intersected with the event that there is a word of length $>n$ in $M$ and, conditioning upon the first such appearing word, we see that the probability that it is followed by something not in $M(\delta)$ is at most $1-c$ and that event is independent on the event we conditioned upon. Notice that this preliminary extension of $B\cap A_1$ is essential to run the independence argument because $A_1$, as defined, imposes restrictions everywhere.

The rest is clear: just choose a fast decreasing sequence $\varepsilon_j$, assume that we start in $M(\varepsilon_1)$, find a word in $M$ followed by a string in $M(\varepsilon_2)$, find a word in $M$ followed by a string in $M(\varepsilon_3)$, etc. The probability that we fail anywhere is at most $3c^{-1}\sum_j \varepsilon_j$ and the event that we start right has probability at least $c-2\varepsilon$.

I hope it is fine but if you see any flaw or an unclear place, let me know :-).

$\endgroup$
  • $\begingroup$ Maybe, some $1-c$ should be replaced to $1-c+2\delta$ in the estimate of probability of the complement of $M(\delta)$, but it seems to be not essential. $\endgroup$ – Fedor Petrov Oct 19 '15 at 22:13
  • $\begingroup$ Yeah, indeed :-) $\endgroup$ – fedja Oct 19 '15 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.