2026-08-21T18:02:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27420 2026-08-21T14:42:39Z ddc:004 open_access

Finite-State Dimension for Continued Fractions: Betting, Entropy and Normality Nandakumar, Satyadev Pulari, Subin S, Akhil Finite-state dimension continued fractions normality finite-state gamblers entropy rates Finite-state dimension quantifies the asymptotic density of information in an infinite sequence as seen by finite automata, and can be viewed as a bounded-memory analogue of Hausdorff dimension. The theory is by now well developed for base-b expansions. In this paper we initiate the study of finite-state dimension in the setting of continued fractions. This setting brings several new difficulties. The natural reference measure is the Gauss measure, which is the canonical invariant probability measure for the Gauss transformation governing the continued fraction shift. Unlike in the base-b setting, however, this measure is not a product measure. In addition, the digit space is inherently infinite, so the symbolic setting is markedly less rigid than the usual finite-alphabet framework. Continued fraction analogues of effective dimension have received considerable attention in recent years, but a finite-state theory in this setting has so far been missing. Finite-state dimension in the classical setting admits several equivalent formulations. We begin from the original finite-state s-gale viewpoint. In the continued fraction setting, however, the betting odds are no longer fixed in advance: unlike in the base-b case, the fair payoff for the next symbol is determined by conditional Gauss probabilities, and these vary with the current continued fraction cylinder. This makes the choice of a finite-state betting model genuinely nontrivial. We first examine a natural local finite-state betting model for truncated continued fraction digits, in which a gambler may use both the visible local context and an additional finite internal memory. We show that this model is too strong: there is a fixed finite-state gambler that wins at a positive exponential rate on every continued fraction normal point. Consequently, full dimension in this model does not characterize continued fraction normality, and the classical Schnorr-Stimm dichotomy fails. We then isolate the source of this failure and introduce a restricted context-gambler model in which the gambler is allowed to use only the visible truncated context, with no additional hidden finite-state memory. For this restricted model, we obtain, in direct analogy with the base-b setting, an entropy-rate characterization of finite-state dimension in terms of conditional entropy rates, and from this derive an exact finite-state characterization of continued fraction normality: an irrational real has finite-state dimension 1 if and only if its continued fraction expansion is normal. Finally, we prove that the Schnorr-Stimm dichotomy does hold in this restricted setting: on a continued fraction normal point every such gambler either preserves constant capital or loses at an exponential rate, while on every non-normal point some such gambler wins at an exponential rate. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Satyadev Nandakumar and Subin Pulari and Akhil S 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.39 urn:nbn:de:0030-drops-274208 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.39 eng https://creativecommons.org/licenses/by/4.0/legalcode