Ehrenfeucht–Mycielski sequence

The sequence starts with the single bit 0; each successive digit is formed by finding the longest suffix of the sequence that also occurs earlier within the sequence, and complementing the bit following the most recent earlier occurrence of that suffix. (The empty string is a suffix and prefix of every string.) For example, the first few steps of this construction process are:

1. 0: initial bit
2. 01: the suffix "" of "0" occurs earlier, most-recently followed by a 0, so add 1
3. 010: the suffix "" of "01" occurs earlier, most-recently followed by a 1, so add 0
4. 0100: the suffix "0" of "010" occurs earlier, most-recently followed by a 1, so add 0
5. 01001: the suffix "0" of "0100" occurs earlier, most-recently followed by a 0, so add 1
6. 010011: the suffix "01" of "01001" occurs earlier, most-recently followed by a 0, so add 1
7. 0100110: the suffix "1" of "010011" occurs earlier, most-recently followed by a 1, so add 0

The first few digits of the sequence are:

010011010111000100001111... (sequence A038219 in the OEIS).

A naive algorithm that generates each bit in the sequence by comparing each suffix with the entire previous sequence could take as much as ${\displaystyle O(n^{3})}$ time to generate the first ${\displaystyle n}$ bits of the sequence. However, as Herman & Soltys (2009) show using a data structure related to a suffix tree, the sequence can be generated much more efficiently, in constant time per generated digit.

The sequence is disjunctive, meaning that every finite subsequence of bits occurs contiguously, infinitely often within the sequence (Ehrenfeucht & Mycielski 1992). More explicitly, the position by which every subsequence of length ${\displaystyle i}$ can be guaranteed to have occurred at least ${\displaystyle j}$ times is at most ${\displaystyle A(4i,j)}$ where ${\displaystyle A}$ is the Ackermann function (Herman & Soltys 2009). Experimentally, however, each subsequence appears much earlier in this sequence than this upper bound would suggest: the position by which all length-${\displaystyle i}$ sequences occur, up to the limit of experimental testing, is close to the minimum possible value it could be, ${\displaystyle 2^{i}+i}$, the position by which a de Bruijn sequence contains all length-${\displaystyle i}$ substrings (Sutner 2003).

Ehrenfeucht & Mycielski (1992) conjecture that the numbers of 0 and 1 bits each converge to a limiting density of 1/2. That is, if ${\displaystyle f(i)}$ denotes the number of 0 bits in the first ${\displaystyle i}$ positions of the Ehrenfeucht–Mycielski sequence, then it should be the case that

${\displaystyle \lim _{i\rightarrow \infty }{\frac {f(i)}{i}}={\frac {1}{2}}.}$

More strongly, I. J. Good suggests that the convergence rate of this limit should be significantly faster than that of a random binary sequence, for which (by the law of the iterated logarithm)

${\displaystyle {\frac {f(i)}{i}}={\frac {1}{2}}+O({\sqrt {\frac {\log \log i}{i}}})}$

(Ehrenfeucht & Mycielski 1992). The Ehrenfeucht–Mycielski balance conjecture suggests that the binary number 0.01001101... (the number having the Ehrenfeucht–Mycielski sequence as its sequence of binary digits after the binary point) may be a normal number in base 2. As of 2009 this conjecture remains unproven (Herman & Soltys 2009); however, it is known that every limit point of the sequence of values ${\displaystyle f(i)/i}$ lies between 1/4 and 3/4 inclusive (Kieffer & Szpankowski 2007).

• Ehrenfeucht, Andrzej; Mycielski, Jan (1992), Guy, Richard K. (ed.), "A pseudorandom sequence: how random is it?", Unsolved problems, American Mathematical Monthly, 99 (4): 373–375, doi:10.2307/2324917, JSTOR 2324917
• Herman, Grzegorz; Soltys, Michael (2009), "On the Ehrenfeucht–Mycielski sequence", Journal of Discrete Algorithms, 7 (4): 500–508, doi:10.1016/j.jda.2009.01.002
• Kieffer, John C.; Szpankowski, Wojciech (2007), "On the Ehrenfeucht–Mycielski balance conjecture", Proc. Conf. Analysis of Algorithms (AofA 2007), Discrete Mathematics and Theoretical Computer Science, pp. 19–28
• Sutner, Klaus (2003), "The Ehrenfeucht–Mycielski sequence" (PDF), in Ibarra, O. H.; Dang, Z. (eds.), Proc. Conf. Implementation and Application of Automata (CIAA 2003), Lecture Notes in Computer Science, 2759, Springer-Verlag, pp. 73–82, doi:10.1007/3-540-45089-0_26

• Propp, Jim (October 16, 2019), "Guess Again: The Ehrenfeucht–Mycielski Sequence", Mathematical Enchantments