Normality of the Ehrenfeucht-Mycielski Sequence

We study the binary Ehrenfeucht Mycielski sequence seeking a balance between the number of occurrences of different binary strings. There have been numerous attempts to prove the balance conjecture of the sequence, which roughly states that 1 and 0 occur equally often in it. Our contribution is twof...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-10
Main Authors: Krishna, Kundan, Nandakumar, Satyadev
Format: Article
Language:English
Subjects:
Normality
Strings
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the binary Ehrenfeucht Mycielski sequence seeking a balance between the number of occurrences of different binary strings. There have been numerous attempts to prove the balance conjecture of the sequence, which roughly states that 1 and 0 occur equally often in it. Our contribution is twofold. First, we study weaker forms of the conjecture proved in the past and lay out detailed proofs for many lemmas which were stated without proofs. Secondly, we extend the claim of balance to that of normality and prove a weaker form of simple normality to word length 2.
ISSN:2331-8422