Skip to main content

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

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 460