文章基本信息

标题：Asymptotic Divergences and Strong Dichotomy
本地全文：下载
作者：Xiang Huang ; Jack H. Lutz ; Elvira Mayordomo 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：51:1-51:15
DOI：10.4230/LIPIcs.STACS.2020.51
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：finite-state dimension; finite-state gambler; Kullback-Leibler divergence; normal sequences