Frecuencia asintótica de$[0,\,1,\,1]$ en la secuencia de Thue-Morse

Question

Deje $t_n$ ser el Thue–Morse secuencia: $$[\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$$ Ver esta pregunta para una definición y fórmula para $t_n$.

Vamos a dividir la secuencia en que no se superponen las carreras de la longitud de la $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$$ Hay $6$ diferentes tipos o carreras en esta secuencia: todas las combinaciones posibles de $0$ e $1$ excepto $[0,\,0,\,0]$ e $[1,\,1,\,1]$ - el Thue–Morse secuencia es el cubo libre.

¿Cuál es la forma asintótica de la frecuencia de la $\underline{[0,\,1,\,1]}$ ejecutar?

Empíricamente, parece ser alrededor de $\style{color:#bbbbbb;text-decoration:line-through}{1/5}\,1/6$, pero la convergencia es muy lenta y errática.

Answer 1

ACTUALIZACIÓN: Algunas reflexiones al final de la OP no se superponen caso, y ahora no estoy tan seguro de la fracción permanece $1/6$ más.

---

Una prueba de que en la superposición en el caso de la fracción es $1/6$.

Deje $a(n) =$ el número de $1$s en el binario de expansión de $n$. De acuerdo a wikipedia, la $n$th poco de la Thue-Morse secuencia $t_n = 0$ si $a(n)$ es aún, y $t_n = 1$ si $a(n)$ es impar.

Reclamo: $[t_n, t_{n+1}, t_{n+2}] = [0,1,1]$ iff la expresión binaria de $n$ tiene la forma:

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

donde $k$ es incluso (incl. $k=0$) y $B$ es cualquier secuencia binaria (incl. secuencia vacía) con un número de $1$s.

Prueba:el Primero de todos, el bit menos significativo (LSB) de $n$ no puede ser $1$. Suponer para el futuro de la contradicción que $LSB(n) = 1$, a continuación, $LSB(n+1) = 0$ e $LSB(n+2) = 1$ y mientras que va de $n+1$ a $n+2$ todos los demás bits de no cambiar. Por lo $t_{n+1} \neq t_{n+2}$, lo que contradice la $[0,1,1]$ requisito.

Ahora que $LSB(n) = 0$, tenemos $a(n+1) = a(n)+1$, lo $t_{n+1} \neq t_n$ como se requiere. A continuación, considere la secuencia más larga de $1$s anteriores a la LSB de $n$, y decir que su longitud es $k$. La última $k+2$ bits de $n+1$ son por lo tanto $01...1$ con $k+1$ final $1$s. Esto significa que la última $k+2$ bits de $n+2$ se $10...0$ con $k+1$ final $0$s. El resto de los bits no cambiar, por lo que el requisito de $t_{n+2} = t_{n+1} \implies k+1$ es impar, es decir, $k$ es incluso.

Finalmente, se puede pre-fix con cualquier $B$, y tenemos la necesidad de $t_n = 0$, lo $B$ debe tener un número par de $1$s, que junto con un $k$ número de $1$s dar lugar a un total de no. de $1$s. QED

Corolario: En el límite, la fracción de números de la forma $B01^k10$ para un determinado $k$ es $2^{-(k+3)}$. Un factor de $2^{-(k+2)}$ proviene de la exigencia de que el final $k+2$ bits especificados, y otro factor de $2^{-1}$ proviene de la exigencia de que $B$ debe tener un número par de $1$s. De modo que la fracción total, sumando todos los $k$, es:

$$\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}$$

Por lo que este responde a la superposición de caso.

---

El que no se superponen caso es equivalente a la restricción de la partida $n$ a múltiplos de $3$. Vamos a:

• $S =$ el conjunto de valores de $n$ s.t. la expresión binaria de $n$ es de la forma $B01^k0$, donde $B$ tiene un número de $1$s y $k$ es incluso.

• $T =$ el conjunto de no-negativo múltiplos de $3$.

Entonces cualquier $n \in S \cap T$ iba a iniciar una $[0,1,1]$ triplete en el OP no la superposición de secuencia.

El OP está pidiendo la "fracción" ${|S \cap T| \over |T|}$. Si esta "fracción" permanecerán ${1\over 6}$, luego de la "fracción" ${|S\cap T| \over |\mathbb{N}|} = {1 \over 18}$. Combinada con la anterior (superpuestas) resultado de que ${|S| \over |\mathbb{N}|} = {1 \over 6}$, esto implica ${|S\cap T| \over |S|} = {1 \over 3}$.

De manera informal, todo esto está diciendo la membresía en $S$ y la pertenencia a $T$ debe ser "ortogonal" o "independiente". Sin embargo, en mi humilde opinión primeros resultados numéricos son... menos independiente de lo que esperaba.

Considere la posibilidad de la expresión binaria $B01^k0$ para algunos $n \in S$. Observe que cualquier par adyacente de los dígitos que son de $1$s tiene un valor de $2q + q$ para algunos $q$ (un poder de $2$), y por lo tanto contribuir $0$ cuando se evaluó mod $3$. Obviamente, detrás de la $0$s no importa. Por lo tanto:

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

Por lo que cualquier $n = B01^k0 \in S$ es un múltiplo de a$3$ fib $B$ (interpretado como un número binario) es un múltiplo de a$3$. La única restricción en $B$ es que pertenece al conjunto de "mal" números de $E$:

• $E =$ el conjunto de cadenas binarias (o equiv., los números binarios expresiones) con un número de $1$s.

Así que la pregunta se convierte en si $T$ e $E$ son "ortogonales", es decir, ${|T \cap E| \over |E|} = {1 \over 3}$? Desde ${|E| \over |\mathbb{N}|} = {1 \over 2}$ esto se convierte aún más en si ${|T \cap E| \over |T|} = {1 \over 2}$?

Y aquí es donde la evidencia numérica es sorprendente. De acuerdo a este OEIS lista de "malos" los números, la mayoría de los primeros múltiplos de$3$ están mal! I. e. al menos entre los primeros números, no son ortogonales a todos.

He intentado de todo $24$ poco los números, y se encontró a${|T \cap E| \over |T|} \approx 0.53$, que es la más distante de la "nominal" $0.5$ de lo que me esperaba...