License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.73
URN: urn:nbn:de:0030-drops-127424
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12742/
Go to the corresponding LIPIcs Volume Portal

Nandakumar, Satyadev ; Vishnoi, Prateek

Randomness and Effective Dimension of Continued Fractions

pdf-format:
LIPIcs-MFCS-2020-73.pdf (0.5 MB)

Abstract

Recently, Scheerer [Adrian-Maria Scheerer, 2017] and Vandehey [Vandehey, 2016] showed that normality for continued fraction expansions and base-b expansions are incomparable notions. This shows that at some level, randomness for continued fractions and binary expansion are different statistical concepts. In contrast, we show that the continued fraction expansion of a real is computably random if and only if its binary expansion is computably random.
To quantify the degree to which a continued fraction fails to be effectively random, we define the effective Hausdorff dimension of individual continued fractions, explicitly constructing continued fractions with dimension 0 and 1.

BibTeX - Entry

@InProceedings{nandakumar_et_al:LIPIcs:2020:12742,
  author =	{Satyadev Nandakumar and Prateek Vishnoi},
  title =	{{Randomness and Effective Dimension of Continued Fractions}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{73:1--73:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12742},
  URN =		{urn:nbn:de:0030-drops-127424},
  doi =		{10.4230/LIPIcs.MFCS.2020.73},
  annote =	{Keywords: Continued fractions, Martin-L{\"o}f randomness, Computable randomness, effective Fractal dimension}
}

Keywords: Continued fractions, Martin-Löf randomness, Computable randomness, effective Fractal dimension
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI