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



partition of infinite word onto permitted words
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 :-).


