Covering sequences of words

Question

(If anyone has a better title please change it!)

Given two finite words $v,w$ in the alphabet $\{a,b\}$, define the $v$-proportion of $w$ to be the largest number of letters in $w$ which can be covered by (not necessarily disjoint) copies of the word $v$ divided by the length of $w$. Denote this quantity by $Pr(w;v)$.

As an example, $Pr(a^7ba^7b;a^4)=7/8$, but $Pr(a^7ba^7b;a^8)=0$.

I would like to find a family of finite words $w_i$ in the alphabet $\{a,b\}$ with the following properties:

For every $n$, $\limsup_i Pr(w_i,a^n)=\alpha_n>0$ but $\limsup_n \alpha_n=0$.

Answer 1

Try $w_0 = b$, $w_1 = bab$, $w_2 = baba^2bab$, $w_3 = baba^2baba^3baba^2bab$, and recursively $w_{i+1} = w_ia^{i+1}w_i$.

Then $\displaystyle \limsup_{i \rightarrow \infty} Pr(w_i,a^n) = \lim_{i \rightarrow \infty} \frac{2^{i + 2 - n} +n - i -3}{3\cdot 2^i - i - 2} = \frac{2^{2-n}}{3} \rightarrow_n 0$.

-Danny "Likes Anything That Resembles a Zimin Word" Rorabaugh