000106698 001__ 106698 000106698 005__ 20230519145500.0 000106698 0247_ $$2doi$$a10.1109/TIT.2021.3085425 000106698 0248_ $$2sideral$$a124623 000106698 037__ $$aART-2021-124623 000106698 041__ $$aeng 000106698 100__ $$aHuang, Xiang 000106698 245__ $$aAsymptotic Divergences and Strong Dichotomy 000106698 260__ $$c2021 000106698 5060_ $$aAccess copy available to the general public$$fUnrestricted 000106698 5203_ $$a—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. 000106698 536__ $$9info:eu-repo/grantAgreement/ES/MICINN/PID2019-104358RB-I00$$9info:eu-repo/grantAgreement/ES/MICINN/TIN2016-80347-R 000106698 540__ $$9info:eu-repo/semantics/openAccess$$aAll rights reserved$$uhttp://www.europeana.eu/rights/rr-f/ 000106698 590__ $$a2.978$$b2021 000106698 592__ $$a1.731$$b2021 000106698 594__ $$a6.2$$b2021 000106698 591__ $$aENGINEERING, ELECTRICAL & ELECTRONIC$$b122 / 277 = 0.44$$c2021$$dQ2$$eT2 000106698 593__ $$aInformation Systems$$c2021$$dQ1 000106698 591__ $$aCOMPUTER SCIENCE, INFORMATION SYSTEMS$$b91 / 164 = 0.555$$c2021$$dQ3$$eT2 000106698 593__ $$aComputer Science Applications$$c2021$$dQ1 000106698 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/acceptedVersion 000106698 700__ $$aLutz, Jack H 000106698 700__ $$0(orcid)0000-0002-9109-5337$$aMayordomo, Elvira$$uUniversidad de Zaragoza 000106698 700__ $$aStull, Donald M 000106698 7102_ $$15007$$2570$$aUniversidad de Zaragoza$$bDpto. Informát.Ingenie.Sistms.$$cÁrea Lenguajes y Sistemas Inf. 000106698 773__ $$g67, 10 (2021), 6296-6305$$pIEEE trans. inf. theory$$tIEEE TRANSACTIONS ON INFORMATION THEORY$$x0018-9448 000106698 8564_ $$s404643$$uhttps://zaguan.unizar.es/record/106698/files/texto_completo.pdf$$yPostprint 000106698 8564_ $$s3447454$$uhttps://zaguan.unizar.es/record/106698/files/texto_completo.jpg?subformat=icon$$xicon$$yPostprint 000106698 909CO $$ooai:zaguan.unizar.es:106698$$particulos$$pdriver 000106698 951__ $$a2023-05-18-14:55:45 000106698 980__ $$aARTICLE