Discrete Mathematics & Theoretical Computer Science |

- 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 EM-sequence. The balance conjecture for the EM-sequence, still open, is the conjecture that the sequence of EM-sequence 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 EM-sequence.

Source: HAL:hal-01184790v1

Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)

Section: Proceedings

Published on: January 1, 2007

Imported on: May 10, 2017

Keywords: Ehrenfeucht-Mycielski sequence,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Funding:

- Source : OpenAIRE Graph
*Crossroads of Information Theory and Computer Science: Analytic Algorithmics, Combinatorics, and Information Theory*; Funder: National Science Foundation; Code: 0513636*Combinatorial &Probabilistic Methods for Biol Sequences*; Funder: National Institutes of Health; Code: 5R01GM068959-04*Algorithmic Theory of Universal Source Coding with a Fidelity Criterion and Related Topics*; Funder: National Science Foundation; Code: 9508282*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*Algorithms for Data Compression Based on Grammars and Trees*; Funder: National Science Foundation; Code: 9902081

This page has been seen 237 times.

This article's PDF has been downloaded 413 times.