Dimension 1 sequences are close to randoms

Noam Greenberg, Joseph S. Miller, Alexander Shen, Linda Brown Westrick

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


We show that a sequence has effective Hausdorff dimension 1 if and only if it is coarsely similar to a Martin-Löf random sequence. More generally, a sequence has effective dimension s if and only if it is coarsely similar to a weakly s-random sequence. Further, for any s<t, every sequence of effective dimension s can be changed on density at most H−1(t)−H−1(s) of its bits to produce a sequence of effective dimension t, and this bound is optimal.

Original languageEnglish (US)
Pages (from-to)99-112
Number of pages14
JournalTheoretical Computer Science
StatePublished - Jan 1 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Dimension 1 sequences are close to randoms'. Together they form a unique fingerprint.

Cite this