000106578 001__ 106578 000106578 005__ 20210902121629.0 000106578 0247_ $$2doi$$a10.4230/LIPIcs.STACS.2020.51 000106578 0248_ $$2sideral$$a117237 000106578 037__ $$aART-2020-117237 000106578 041__ $$aeng 000106578 100__ $$aHuang, Xiang 000106578 245__ $$aAsymptotic divergences and strong dichotomy 000106578 260__ $$c2020 000106578 5060_ $$aAccess copy available to the general public$$fUnrestricted 000106578 5203_ $$aThe Schnorr-Stimm dichotomy theorem [31] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet S. 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||a) of a probability measure a on S from a sequence S over S and the upper asymptotic divergence Div(S||a) of a from S in such a way that a sequence S is a-normal (meaning that every string w has asymptotic frequency a(w) in S) if and only if Div(S||a) = 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 a-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 2Div(S||a)|w| . (20) The exponential rate of loss in 2 is 2-RiskG(w) . We also use (10) to show that 1 - Div(S||a)/c, where c = log(1/mina¿S a(a)), is an upper bound on the finite-state a-dimension of S and prove the dual fact that 1 - div(S||a)/c is an upper bound on the finite-state strong a-dimension of S. 000106578 536__ $$9info:eu-repo/grantAgreement/ES/MICINN/TIN2016-80347-R 000106578 540__ $$9info:eu-repo/semantics/openAccess$$aby$$uhttp://creativecommons.org/licenses/by/3.0/es/ 000106578 592__ $$a0.54$$b2020 000106578 593__ $$aSoftware$$c2020 000106578 593__ $$aLogic$$c2020 000106578 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/publishedVersion 000106578 700__ $$aLutz, Jack H. 000106578 700__ $$0(orcid)0000-0002-9109-5337$$aMayordomo, Elvira$$uUniversidad de Zaragoza 000106578 700__ $$aStull, Donald M. 000106578 7102_ $$15007$$2570$$aUniversidad de Zaragoza$$bDpto. Informát.Ingenie.Sistms.$$cÁrea Lenguajes y Sistemas Inf. 000106578 773__ $$g154 (2020), 51 [15 pp.]$$pLeibniz int. proc. inform.$$tLeibniz international proceedings in informatics$$x1868-8969 000106578 8564_ $$s542585$$uhttps://zaguan.unizar.es/record/106578/files/texto_completo.pdf$$yVersión publicada 000106578 8564_ $$s1921066$$uhttps://zaguan.unizar.es/record/106578/files/texto_completo.jpg?subformat=icon$$xicon$$yVersión publicada 000106578 909CO $$ooai:zaguan.unizar.es:106578$$particulos$$pdriver 000106578 951__ $$a2021-09-02-08:51:58 000106578 980__ $$aARTICLE