Let $w=a\_1a\_2a\_3...$ be an infinite word over a finite alphabet and $\epsilon>0$. Do there exist integers $n,k$ such that $\frac{d(a\_1a\_2...a\_n,a\_{k+1}a\_{k+2}...a\_{k+n})}{n}<\epsilon$ ?
($d(u,v)$ is the hamming distence)



Conjecture about infinite word
OK, let's go over it slowly.


The alphabet will consist of 4 symbols: $x,u,b,c$.


The infinite word will be $xU\_1Q\_2U\_3Q\_4U\_5Q\_6\dots$ where $U\_m$ is the finite word consisting of $m$ symbols $u$ and $Q\_m$ is the *random* word consisting of $m$ symbols each of which is $b$ or $c$ with probability $1/2$ with the convention that the choices of symbols at different positions are independent. So you get something like
$$
xubcuuubcbbuuuuucbbccbuuuuuuucccbcbbb\dots
$$ 


It is easy to check (see the discussion [here](https://academia.stackexchange.com/questions/130454/is-there-any-good-reason-to-write-it-is-easy-to-see)) that as $n\to\infty$, the string $a\_1a\_2\dots a\_n$ contains one symbol $x$ ($a\_1=x$), $\frac n2+O(\sqrt n)$ symbols $u$ and $\frac n2+O(\sqrt n)$ symbols each of which is $b$ or $c$.


Now suppose that $n$ is large enough and $k>n^2$. Then the $u$'s in the word $a\_{k+1}a\_{k+2}\dots a\_{k+n}$ form a single block and the non-$u$'s form another block. One of these blocks has length $\ell \ge n/2$. However, the corresponding block in $a\_1a\_2\dots a\_n$ is occupied by $\frac \ell 2+O(\sqrt n)$ symbols $u$ and $\frac \ell 2+O(\sqrt n)$ symbols that are not $u$, so the Hamming distance in question is at least 
$\frac \ell 2+O(\sqrt n)\ge \frac n4+O(\sqrt n)\ge \frac n5$ if $n\ge n\_0$.


Thus we need to look only at $k\le n^2$ for large $n$. We have $\frac n2+O(\sqrt n)$ random symbols in $a\_1a\_2\dots a\_n$ and, for fixed $k\ge 1$, the probability that each of them is matched in $a\_{k+1}a\_{k+2}\dots a\_{k+n}$ is $0$ or $1/2$, the corresponding events being independent. Thus, the chance that we have at least $\frac n3$ matchings instead of expected $\le\frac n4$ is at most $Ce^{-cn}$ by the Bernstein (a.k.a. Chernov, Hoeffding, etc.) bound. Since the series $\sum\_n Cn^2e^{-cn}$ converges, we conclude that with probability close to $1$, the Hamming distance in question is at least $\frac n6+O(\sqrt n)>\frac n7$ for all $n\ge n\_0$, $k\le n^2$.


Finally, due to the uniqueness of $x$ in the word, the Hamming distance is always at least $1$, so the ratio in question is never less than $\min(\frac 17,\frac 1{n\_0})$.


I hope it is clearer now but feel free to ask questions if something is still confusing.


By the way, the word "conjecture" means "a statement supported by extensive circumstantial evidence and several rigorous partial results", not "something that just came to my head" or "something I want to be true", so, since you put it in the title, I wonder what positive results you can prove here.


