Asymptotic Divergences and Strong Dichotomy

• Published in: IEEE transactions on information theory 2021-10, Vol.67 (10), p.6296-6305
• Main Authors: Huang, Xiang, Lutz, Jack H., Mayordomo, Elvira, Stull, Donald M.
• Format: Article
• Language: English
• Subjects: Asymptotic methods; Asymptotic properties; Divergence; Entropy; Finite-state dimension; finite-state gambler; Frequency measurement; Gambling; Kullback-Leibler divergence; Length measurement; normal sequences; Normality; Random variables; Strings; Technological innovation; Theorems; Upper bound; Upper bounds
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2021.3085425

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 \Sigma . 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 {\mathrm {div}}(S||\alpha) of a probability measure \alpha on \Sigma from a sequence S over \Sigma and the upper asymptotic divergence {\mathrm {Div}}(S||\alpha) of \alpha from S in such a way that a sequence S is \alpha -normal (meaning that every string w has asymptotic frequency \alpha (w) in S ) if and only if