Secuencia de Ehrenfeucht-Mycielski

La secuencia de Ehrenfeucht-Mycielski es una secuencia recursiva de dígitos binarios con propiedades pseudoaleatorias , definida por Andrzej Ehrenfeucht y Jan Mycielski  (1992).

Definición

La secuencia comienza con un único bit, el 0; cada dígito sucesivo se forma buscando el sufijo más largo de la secuencia que también aparece antes en la secuencia y complementando el bit que sigue a la aparición anterior más reciente de ese sufijo. (La cadena vacía es un sufijo y un prefijo de cada cadena). Por ejemplo, los primeros pasos de este proceso de construcción son: ^[1]

1. 0: bit inicial
2. 01: el sufijo "" de "0" aparece antes, más recientemente, seguido de un 0, por lo que se agrega 1
3. 010: el sufijo "" de "01" aparece antes, más recientemente, seguido de un 1, por lo que se agrega 0
4. 0100: el sufijo "0" de "010" aparece antes, más recientemente, seguido de un 1, por lo que se agrega 0
5. 01001: el sufijo "0" de "0100" aparece antes, más recientemente, seguido de un 0, por lo que se debe agregar 1
6. 010011: el sufijo "01" de "01001" aparece antes, más recientemente, seguido de un 0, por lo que se debe agregar 1
7. 0100110: el sufijo "1" de "010011" aparece antes, más recientemente, seguido de un 1, por lo que se debe agregar 0

Los primeros dígitos de la secuencia son: ^[1]

010011010111000100001111...

Algoritmos

Un algoritmo ingenuo que genere cada bit de la secuencia comparando cada sufijo con toda la secuencia anterior podría tardar tanto como tiempo en generar los primeros bits de la secuencia. Sin embargo, utilizando una estructura de datos relacionada con un árbol de sufijos , la secuencia se puede generar de manera mucho más eficiente, en tiempo constante por dígito generado. ^[2] ${\displaystyle O(n^{3})}$ ${\displaystyle n}$

Universalidad

La secuencia es disyuntiva , lo que significa que cada subsecuencia finita de bits ocurre de forma contigua, infinitamente a menudo dentro de la secuencia. ^[3] Más explícitamente, la posición por la cual se puede garantizar que cada subsecuencia de longitud ha ocurrido al menos veces es como máximo donde es la función de Ackermann . ^[2] Experimentalmente, sin embargo, cada subsecuencia aparece mucho antes en esta secuencia de lo que sugeriría este límite superior: la posición por la cual ocurren todas las secuencias de longitud, hasta el límite de las pruebas experimentales, está cerca del valor mínimo posible que podría ser, , la posición por la cual una secuencia de De Bruijn contiene todas las subcadenas de longitud. ^[4] ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle A(4i,j)}$ ${\displaystyle A}$ ${\displaystyle i}$ ${\displaystyle 2^{i}+i}$ ${\displaystyle i}$

Normalidad

Problema sin resolver en matemáticas :

¿Es el número binario 0.01001101... normal?

(más problemas sin resolver en matemáticas)

Ehrenfeucht y Mycielski (1992) conjeturan que los números de bits 0 y 1 convergen cada uno a una densidad límite de 1/2. Es decir, si denota el número de bits 0 en las primeras posiciones de la secuencia de Ehrenfeucht–Mycielski, entonces debería ser el caso que Más firmemente, IJ Good sugiere que la tasa de convergencia de este límite debería ser significativamente más rápida que la de una secuencia binaria aleatoria , para la cual (por la ley del logaritmo iterado ) ^[3] La conjetura de equilibrio de Ehrenfeucht–Mycielski sugiere que el número binario 0,01001101... (el número que tiene la secuencia de Ehrenfeucht–Mycielski como su secuencia de dígitos binarios después del punto binario) puede ser un número normal en base 2 . A partir de 2009 esta conjetura sigue sin demostrarse; ^[2] Sin embargo, se sabe que cada punto límite de la secuencia de valores se encuentra entre 1/4 y 3/4 inclusive. ^[5] ${\displaystyle f(i)}$ ${\displaystyle i}$ $${\displaystyle \lim _{i\rightarrow \infty }{\frac {f(i)}{i}}={\frac {1}{2}}.}$$ $${\displaystyle {\frac {f(i)}{i}}={\frac {1}{2}}+O\left({\sqrt {\frac {\log \log i}{i}}}\right).}$$ ${\displaystyle f(i)/i}$

Referencias

1. Sloane, N. J. A. (ed.), "Secuencia A038219 (La secuencia de Ehrenfeucht-Mycielski (versión 0,1): una secuencia máximamente impredecible)", La enciclopedia en línea de secuencias de enteros , OEIS Foundation
2. Herman, Grzegorz; Soltys, Michael (2009), "Sobre la secuencia de Ehrenfeucht-Mycielski", Journal of Discrete Algorithms , 7 (4): 500–508, doi : 10.1016/j.jda.2009.01.002
3. Ehrenfeucht, Andrzej ; Mycielski, Jan (1992), Guy, Richard K. (ed.), "Una secuencia pseudoaleatoria: ¿cuán aleatoria es?", Problemas sin resolver, American Mathematical Monthly , 99 (4): 373–375, doi :10.2307/2324917, JSTOR  2324917
4. Sutner, Klaus (2003), "La secuencia Ehrenfeucht-Mycielski" (PDF) , en Ibarra, OH ; Dang, Z. (eds.), Proc. Conf. Implementación y aplicación de autómatas (CIAA 2003) , Lecture Notes in Computer Science, vol. 2759, Springer-Verlag, págs. 73–82, doi :10.1007/3-540-45089-0_26
5. Kieffer, John C.; Szpankowski, Wojciech (2007), "Sobre la conjetura de equilibrio de Ehrenfeucht–Mycielski", Proc. Conf. Análisis de algoritmos (AofA 2007) , Matemáticas discretas y ciencias de la computación teórica, págs. 19-28

Enlaces externos

• Propp, Jim (16 de octubre de 2019), "Adivina otra vez: la secuencia de Ehrenfeucht-Mycielski", Mathematical Enchantments