106698 20230519145500.0 doi 10.1109/TIT.2021.3085425 sideral 124623 ART-2021-124623 eng Huang, Xiang Asymptotic Divergences and Strong Dichotomy 2021 Access copy available to the general public Unrestricted —The Schnorr-Stimm dichotomy theorem [31] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, or 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 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 RiskG(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. (10 ) The infinitely-often exponential rate of winning in 1 is 2 Div(S||α)|w| . (20 ) The exponential rate of loss in 2 is 2 − RiskG(w) . We also use (10 ) to show that 1 − Div(S||α)/c, where c = log(1/mina∈Σ α(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. info:eu-repo/grantAgreement/ES/MICINN/PID2019-104358RB-I00 info:eu-repo/grantAgreement/ES/MICINN/TIN2016-80347-R info:eu-repo/semantics/openAccess All rights reserved http://www.europeana.eu/rights/rr-f/ 2.978 2021 ENGINEERING, ELECTRICAL & ELECTRONIC 122 / 277 = 0.44 2021 Q2 T2 COMPUTER SCIENCE, INFORMATION SYSTEMS 91 / 164 = 0.555 2021 Q3 T2 1.731 2021 Information Systems 2021 Q1 Computer Science Applications 2021 Q1 6.2 2021 info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion Lutz, Jack H Mayordomo, Elvira Universidad de Zaragoza (orcid)0000-0002-9109-5337 Stull, Donald M 5007 570 Universidad de Zaragoza Dpto. Informát.Ingenie.Sistms. Área Lenguajes y Sistemas Inf. 67, 10 (2021), 6296-6305 IEEE trans. inf. theory IEEE TRANSACTIONS ON INFORMATION THEORY 0018-9448 404643 http://zaguan.unizar.es/record/106698/files/texto_completo.pdf Postprint 3447454 http://zaguan.unizar.es/record/106698/files/texto_completo.jpg?subformat=icon icon Postprint oai:zaguan.unizar.es:106698 articulos driver 2023-05-18-14:55:45 ARTICLE