Asymptotic Divergences and Strong Dichotomy

Huang, Xiang ; Lutz, Jack H ; Mayordomo, Elvira (Universidad de Zaragoza) ; Stull, Donald M

Resumen: —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.

Idioma: Inglés

DOI: 10.1109/TIT.2021.3085425

Año: 2021

Publicado en: IEEE TRANSACTIONS ON INFORMATION THEORY 67, 10 (2021), 6296-6305
ISSN: 0018-9448

Factor impacto JCR: 2.978 (2021)

Categ. JCR: ENGINEERING, ELECTRICAL & ELECTRONIC rank: 122 / 277 = 0.44 (2021) - Q2 - T2
Categ. JCR: COMPUTER SCIENCE, INFORMATION SYSTEMS rank: 91 / 164 = 0.555 (2021) - Q3 - T2

Factor impacto CITESCORE: 6.2 - Computer Science (Q1) - Social Sciences (Q1)

Factor impacto SCIMAGO: 1.731 - Information Systems (Q1) - Computer Science Applications (Q1)

Financiación: info:eu-repo/grantAgreement/ES/MICINN/PID2019-104358RB-I00
Financiación: info:eu-repo/grantAgreement/ES/MICINN/TIN2016-80347-R

Tipo y forma: Artículo (PostPrint)

Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)