When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2020.51
URN: urn:nbn:de:0030-drops-119125
URL: https://drops.dagstuhl.de/opus/volltexte/2020/11912/
 Go to the corresponding LIPIcs Volume Portal

### Asymptotic Divergences and Strong Dichotomy

 pdf-format:

### Abstract

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.

### 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:1--51:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-140-5},
ISSN =	{1868-8969},
year =	{2020},
volume =	{154},
editor =	{Christophe Paul and Markus Bl{\"a}ser},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},