Asymptotic Divergences and Strong Dichotomy

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\u27) The infinitely-often exponential rate of winning in 1 is 2^{Div(S||?)|w|}. (2\u27) The exponential rate of loss in 2 is 2^{-Risk_G(w)}. We also use (1\u27) 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