John C. Kieffer ; W. Szpankowski

On the EhrenfeuchtMycielski Balance Conjecture
dmtcs:3542 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2007,
DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)

https://doi.org/10.46298/dmtcs.3542
On the EhrenfeuchtMycielski Balance Conjecture
Authors: John C. Kieffer ^{1}; W. Szpankowski ^{2}
NULL##NULL
John C. Kieffer;W. Szpankowski
1 Department of Electrical and Computer Engineering [Minneapolis]
2 Department of Computer Science [Purdue]
In 1992, A. Ehrenfeucht and J. Mycielski defined a seemingly pseudorandom binary sequence which has since been termed the EMsequence. The balance conjecture for the EMsequence, still open, is the conjecture that the sequence of EMsequence initial segment averages converges to $1/2$. In this paper, we do not prove the balance conjecture but we do make some progress concerning it, namely, we prove that every limit point of the aforementioned sequence of averages lies in the interval $[1/4,3/4]$, improving the best previous result that every such limit point belongs to the interval $[0.11,0.89]$. Our approach is novel and exploits an analysis of the growth behavior as $n \to \infty$ of the rooted tree formed by the binary strings appearing at least twice as substrings of the length $n$ initial segment of the EMsequence.
Algorithms for Data Compression Based on Grammars and Trees; Funder: National Science Foundation; Code: 9902081
Combinatorial &Probabilistic Methods for Biol Sequences; Funder: National Institutes of Health; Code: 5R01GM06895904
Collaborative Research: Nonlinear Equations Arising in Information Theory and Computer Sciences; Funder: National Science Foundation; Code: 0503742
Analytic Information Theory, Combinatorics, and Algorithmics: The Precise Redundancy and Related Problems; Funder: National Science Foundation; Code: 0208709
Crossroads of Information Theory and Computer Science: Analytic Algorithmics, Combinatorics, and Information Theory; Funder: National Science Foundation; Code: 0513636
Algorithmic Theory of Universal Source Coding with a Fidelity Criterion and Related Topics; Funder: National Science Foundation; Code: 9508282
Herman, Grzegorz; Soltys, Michael, 2009, On The EhrenfeuchtâMycielski Sequence, Journal Of Discrete Algorithms, 7, 4, pp. 500508, 10.1016/j.jda.2009.01.002.