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
  • Combinatorial &Probabilistic Methods for Biol Sequences; Funder: National Institutes of Health; Code: 5R01GM068959-04


Is related to
  • 1 ScholeXplorer

1 Document citing this article

Consultation statistics

This page has been seen 151 times.
This article's PDF has been downloaded 330 times.