2026-07-23T04:54:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11912 2024-03-06T10:49:00Z ddc:004 open_access

Asymptotic Divergences and Strong Dichotomy Huang, Xiang Lutz, Jack H. Mayordomo, Elvira Stull, Donald M. finite-state dimension finite-state gambler Kullback-Leibler divergence normal sequences The Schnorr-Stimm dichotomy theorem [Schnorr and Stimm, 1972] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S, the following two things are true. (1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S. (2) If S is normal, then any finite-state gambler betting on S loses money at an exponential rate betting on S. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence div(S||α) of a probability measure α on Σ from a sequence S over Σ and the upper asymptotic divergence Div(S||α) of α from S in such a way that a sequence S is α-normal (meaning that every string w has asymptotic frequency α(w) in S) if and only if Div(S||α)=0. We also use the Kullback-Leibler divergence to quantify the total risk Risk_G(w) that a finite-state gambler G takes when betting along a prefix w of S. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to α-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes w of S. (1') The infinitely-often exponential rate of winning in 1 is 2^{Div(S||α)|w|}. (2') The exponential rate of loss in 2 is 2^{-Risk_G(w)}. We also use (1') to show that 1-Div(S||α)/c, where c= log(1/ min_{a∈Σ} α(a)), is an upper bound on the finite-state α-dimension of S and prove the dual fact that 1-div(S||α)/c is an upper bound on the finite-state strong α-dimension of S. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiang Huang and Jack H. Lutz and Elvira Mayordomo and Donald M. Stull 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.51 urn:nbn:de:0030-drops-119125 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.51 eng https://creativecommons.org/licenses/by/3.0/legalcode