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