Asymptotic Divergences and Strong Dichotomy
Xiang Huang, Jack H. Lutz, Elvira Mayordomo, D. M. Stull · IEEE Transactions on Information Theory · 2021
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 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. ( $1~'$ ) The infinitely-often exponential rate of winning in 1 is 2Div(S||α)|w|. ( $2~'$ ) The exponential rate of loss in 2 is 2- RiskG(w). We also use (1 $'$ ) 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.