Skip to main content
Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Draw attention by Fedor Petrov
Bounty Started worth 100 reputation by Fedor Petrov
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

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