Asymptotic frequency of $[0,\,1,\,1]$ in the Thue–Morse sequence

Let $t_n$ be the Thue–Morse sequence: $$[\color{blue}{0,\,1,\,1,\,0,}\,\color{red}{1,\,0,\,0,\,1,}\,\color{blue}{1,\,0,\,0,\,1,}\,\color{red}{0,\,1,\,1,\,0,}\,...].\tag1$$ See this question for a definition and formula for $t_n$.

Let's split the sequence into non-overlapping runs of length $3$: $$[\underline{[\color{blue}{0,\,1,\,1}]},\,[\color{blue}{0,}\,\color{red}{1,\,0}],\,[\color{red}{0,\,1,}\,\color{blue}1],\,[\color{blue}{0,\,0,\,1}],\,\underline{[\color{red}{0,\,1,\,1}]},\,...].\tag2$$ There are $6$ different sorts or runs in this sequence: all possible combinations of $0$ and $1$ except $[0,\,0,\,0]$ and $[1,\,1,\,1]$ — the Thue–Morse sequence is cube-free.

What is the asymptotic frequency of the $\underline{[0,\,1,\,1]}$ run?

Empirically, it seems to be around $\style{color:#bbbbbb;text-decoration:line-through}{1/5}\,1/6$, but the convergence is quite slow and erratic.

UPDATE: Some more thoughts at the end on the OP's non-overlapping case, and now I'm not so sure the fraction remains $1/6$ any more.

A proof that in the overlapping case the fraction is $1/6$.

Let $a(n) =$ the number of $1$s in the binary expansion of $n$. According to wikipedia, the $n$th bit of the Thue-Morse sequence $t_n = 0$ if $a(n)$ is even, and $t_n = 1$ if $a(n)$ is odd.

Claim: $[t_n, t_{n+1}, t_{n+2}] = [0,1,1]$ iff the binary expression of $n$ has the form:

$$B0\overbrace{1...1}^{k \ \text{times}}0, \text{also written as: } B01^k0$$

where $k$ is even (incl. $k=0$) and $B$ is any binary sequence (incl. empty sequence) with an even number of $1$s.

Proof: First of all, the least significant bit (LSB) of $n$ cannot be $1$. Assume for future contradiction that $LSB(n) = 1$, then $LSB(n+1) = 0$ and $LSB(n+2) = 1$ and while going from $n+1$ to $n+2$ all other bits didn't change. So $t_{n+1} \neq t_{n+2}$, which contradicts the $[0,1,1]$ requirement.

Now that $LSB(n) = 0$, we have $a(n+1) = a(n)+1$, so $t_{n+1} \neq t_n$ as required. Next, consider the longest sequence of $1$s preceding the LSB of $n$, and say its length is $k$. The last $k+2$ bits of $n+1$ are therefore $01...1$ with $k+1$ ending $1$s. This means the last $k+2$ bits of $n+2$ are $10...0$ with $k+1$ ending $0$s. The rest of the bits didn't change, so the requirement $t_{n+2} = t_{n+1} \implies k+1$ is odd, i.e. $k$ is even.

Finally, we can pre-fix with any $B$, and we need $t_n = 0$, so $B$ must have an even number of $1$s, which together with an even $k$ number of $1$s result in an even total no. of $1$s. QED

Corollary: In the limit, the fraction of numbers of the form $B01^k10$ for a specific $k$ is $2^{-(k+3)}$. A factor of $2^{-(k+2)}$ comes from the requirement that the ending $k+2$ bits are specified, and another factor of $2^{-1}$ comes from the requirement that $B$ must have an even number of $1$s. So the total fraction, summed over all even $k$, is:

$$\sum_{j=0}^\infty 2^{-(2j+3)} = {1\over 8} \sum_{j=0}^\infty {1\over 4}^j = {1\over 8} {4 \over 3} = {1 \over 6}$$

So this answers the overlapping case.

The non-overlapping case is equivalent to restricting the starting $n$ to multiples of $3$. Let:

• $S =$ the set of values of $n$ s.t. the binary expression of $n$ is of the form $B01^k0$, where $B$ has an even number of $1$s and $k$ is even.

• $T =$ the set of non-negative multiples of $3$.

Then any $n \in S \cap T$ would start a $[0,1,1]$ triplet in the OP's non-overlapping sequence.

The OP is asking for the "fraction" ${|S \cap T| \over |T|}$. If this "fraction" were to remain ${1\over 6}$, then the "fraction" ${|S\cap T| \over |\mathbb{N}|} = {1 \over 18}$. Combined with the previous (overlapping) result that ${|S| \over |\mathbb{N}|} = {1 \over 6}$, this implies ${|S\cap T| \over |S|} = {1 \over 3}$.

Informally, all this is saying membership in $S$ and membership in $T$ must be "orthogonal" or "independent". However, IMHO early numerical results are... less independent than I had hoped.

Consider the binary expression $B01^k0$ for some $n \in S$. Notice that any adjacent pair of digits which are both $1$s have a value of $2q + q$ for some $q$ (a power of $2$), and therefore contribute $0$ when evaluated mod $3$. Obviously, trailing $0$s also don't matter. Therefore:

$$k \text{ is even } \implies B01^k0 = B0^{k+2} = B \pmod 3$$

So any $n = B01^k0 \in S$ is a multiple of $3$ iff $B$ (interpreted as a binary number) is a multiple of $3$. The only restriction on $B$ is that it belongs in the set of "evil" numbers $E$:

• $E =$ the set of binary strings (or equiv., numbers with binary expressions) with an even number of $1$s.

So the question becomes whether $T$ and $E$ are "orthogonal", i.e. ${|T \cap E| \over |E|} = {1 \over 3}$? Since ${|E| \over |\mathbb{N}|} = {1 \over 2}$ this further becomes whether ${|T \cap E| \over |T|} = {1 \over 2}$?

And this is where the numerical evidence is surprising. According to this OEIS list of "evil" numbers, most of the early multiples-of-$3$ are evil! I.e. at least among the early numbers, they are not orthogonal at all.

I tried up to all $24$ bit numbers, and found ${|T \cap E| \over |T|} \approx 0.53$, which is more distant from the "nominal" $0.5$ than I expected...

Since the Thue-Morse sequence is not normal, i.e., every finite $0,1$-block of length $k>1$ does not appear with the same asymptotic frequency $2^{-k}$, it follows that the density of all $0,1$-blocks of length $3$, including $[0,1,1]$, is not equal. This is because there can be no triplets $[0,0,0]$ and $[1,1,1]$ as you rightly noted.

As a consequence, the statement

"The density of triplets $[b,b,b]$, where $b\in\{0,1\}$, excluding $[0,0,0]$ and $[1,1,1]$, equals $\frac16$"

is false.

On the other hand, Mauduit, Rivat and Drmota proved in 2013 that the Thue-Morse sequence along the squares is normal. This implies the following result:

Theorem 1. The density of all triplets, including $[0,0,0]$ and $[1,1,1]$, within the set $S=[t_0,t_1,t_4,t_9,\ldots,t_{n^2},\ldots]$ is $\frac18$.