Abstract
The SchnorrStimm dichotomy theorem [Schnorr and Stimm, 1972] concerns finitestate 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 finitestate gambler that wins money at an infinitelyoften exponential rate betting on S.
(2) If S is normal, then any finitestate gambler betting on S loses money at an exponential rate betting on S.
In this paper we use the KullbackLeibler 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 KullbackLeibler divergence to quantify the total risk Risk_G(w) that a finitestate 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 SchnorrStimm 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 infinitelyoften 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 1Div(Sα)/c, where c= log(1/ min_{a∈Σ} α(a)), is an upper bound on the finitestate αdimension of S and prove the dual fact that 1div(Sα)/c is an upper bound on the finitestate strong αdimension of S.
BibTeX  Entry
@InProceedings{huang_et_al:LIPIcs:2020:11912,
author = {Xiang Huang and Jack H. Lutz and Elvira Mayordomo and Donald M. Stull},
title = {{Asymptotic Divergences and Strong Dichotomy}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {51:151:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11912},
URN = {urn:nbn:de:0030drops119125},
doi = {10.4230/LIPIcs.STACS.2020.51},
annote = {Keywords: finitestate dimension, finitestate gambler, KullbackLeibler divergence, normal sequences}
}
Keywords: 

finitestate dimension, finitestate gambler, KullbackLeibler divergence, normal sequences 
Collection: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) 
Issue Date: 

2020 
Date of publication: 

04.03.2020 