3 Search Results for "Vishnoi, Prateek"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.16
The Agafonov and Schnorr-Stimm Theorems for Probabilistic Automata

Authors: Laurent Bienvenu, Hugo Gimbert, and Subin Pulari

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
For a fixed alphabet A, an infinite sequence X is said to be normal if every word w over A appears in X with the same frequency as any other word of the same length. A classical result of Agafonov (1966) relates normality to finite automata as follows: a sequence X is normal if and only if any subsequence of X selected by a finite automaton is itself normal. Another theorem of Schnorr and Stimm (1972) gives an alternative characterization: a sequence X is normal if and only if no gambler can win large amounts of money by betting on the sequence X using a strategy that can be described by a finite automaton. Both of these theorems are established in the setting of deterministic finite automata. This raises the question as to whether they can be extended to the setting of probabilistic finite automata. In the case of the Agafonov theorem, a partial positive answer was given by Léchine et al. (MFCS 2024) in a restricted case of probabilistic automata with rational transition probabilities. In this paper, we settle the full conjecture by proving that both the Agafonov and the Schnorr-Stimm theorems hold true for arbitrary probabilistic automata. Specifically, we show that a sequence X is normal if and only if any probabilistic automaton selects a normal subsequence of X with probability 1 and also show that a sequence X is normal if and only if any probabilistic finite-state gambler fails to win on X with probability 1.
Cite as

Laurent Bienvenu, Hugo Gimbert, and Subin Pulari. The Agafonov and Schnorr-Stimm Theorems for Probabilistic Automata. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.FSTTCS.2025.16,
  author =	{Bienvenu, Laurent and Gimbert, Hugo and Pulari, Subin},
  title =	{{The Agafonov and Schnorr-Stimm Theorems for Probabilistic Automata}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.16},
  URN =		{urn:nbn:de:0030-drops-250978},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.16},
  annote =	{Keywords: Normality, Agafonov theorem, probabilistic automata}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.70
Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals

Authors: Satyadev Nandakumar, Akhil S, and Prateek Vishnoi

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We establish that constructive continued fraction dimension originally defined using s-gales [Nandakumar and Vishnoi, 2022] is robust, but surprisingly, that the effective continued fraction dimension and effective (base-b) Hausdorff dimension of the same real can be unequal in general. We initially provide an equivalent characterization of continued fraction dimension using Kolmogorov complexity. In the process, we construct an optimal lower semi-computable s-gale for continued fractions. We also prove new bounds on the Lebesgue measure of continued fraction cylinders, which may be of independent interest. We apply these bounds to reveal an unexpected behavior of continued fraction dimension. It is known that feasible dimension is invariant with respect to base conversion [Hitchcock and Mayordomo, 2013]. We also know that Martin-Löf randomness and computable randomness are invariant not only with respect to base conversion, but also with respect to the continued fraction representation [Nandakumar and Vishnoi, 2022]. In contrast, for any 0 < ε < 0.5, we prove the existence of a real whose effective Hausdorff dimension is less than ε, but whose effective continued fraction dimension is greater than or equal to 0.5. This phenomenon is related to the "non-faithfulness" of certain families of covers, investigated by Peres and Torbin [Peres and Torbin] and by Albeverio, Ivanenko, Lebid and Torbin [Albeverio et al., 2020]. We also establish that for any real, the constructive Hausdorff dimension is at most its effective continued fraction dimension.
Cite as

Satyadev Nandakumar, Akhil S, and Prateek Vishnoi. Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2023.70,
  author =	{Nandakumar, Satyadev and S, Akhil and Vishnoi, Prateek},
  title =	{{Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{70:1--70:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.70},
  URN =		{urn:nbn:de:0030-drops-186041},
  doi =		{10.4230/LIPIcs.MFCS.2023.70},
  annote =	{Keywords: Algorithmic information theory, Kolmogorov complexity, Continued fractions, Effective Hausdorff dimension}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.73
Randomness and Effective Dimension of Continued Fractions

Authors: Satyadev Nandakumar and Prateek Vishnoi

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

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.
Cite as

Satyadev Nandakumar and Prateek Vishnoi. Randomness and Effective Dimension of Continued Fractions. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 73:1-73:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nandakumar_et_al:LIPIcs.MFCS.2020.73,
  author =	{Nandakumar, Satyadev and Vishnoi, Prateek},
  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 =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.73},
  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}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023
  • 1 2020

  • Refine by Author
  • 2 Nandakumar, Satyadev
  • 2 Vishnoi, Prateek
  • 1 Bienvenu, Laurent
  • 1 Gimbert, Hugo
  • 1 Pulari, Subin
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Computability
  • 1 Mathematics of computing → Information theory
  • 1 Theory of computation → Constructive mathematics
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 2 Continued fractions
  • 1 Agafonov theorem
  • 1 Algorithmic information theory
  • 1 Computable randomness
  • 1 Effective Hausdorff dimension
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact