# partition of infinite word onto permitted words

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$''.

• 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. – Andreas Blass Apr 30 '14 at 14:18
• 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? – Benjamin Steinberg Apr 30 '14 at 15:36
• 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. – The Masked Avenger Apr 30 '14 at 16:13
• @TheMaskedAvenger, thanks. I misread the question as a finite set of words on my little phone. – Benjamin Steinberg Apr 30 '14 at 18:45

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 :-).

• 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. – Fedor Petrov Oct 19 '15 at 22:13
• Yeah, indeed :-) – fedja Oct 19 '15 at 23:30