John C. Kieffer ; W. Szpankowski - On the Ehrenfeucht-Mycielski Balance Conjecture

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

Authors: John C. Kieffer 1; W. Szpankowski 2

  • 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.

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]
    Source : OpenAIRE Graph
  • Analytic Information Theory, Combinatorics, and Algorithmics: The Precise Redundancy and Related Problems; Funder: National Science Foundation; Code: 0208709
  • Algorithmic Theory of Universal Source Coding with a Fidelity Criterion and Related Topics; Funder: National Science Foundation; Code: 9508282
  • Algorithms for Data Compression Based on Grammars and Trees; Funder: National Science Foundation; Code: 9902081
  • 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
  • Collaborative Research: Nonlinear Equations Arising in Information Theory and Computer Sciences; Funder: National Science Foundation; Code: 0503742

1 Document citing this article

Consultation statistics

This page has been seen 181 times.
This article's PDF has been downloaded 360 times.