Asymptotic Divergences and Strong Dichotomy

Abstract

The Schnorr-Stimm dichotomy theorem concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet $\Sigma$. In this paper we use the Kullback-Leibler divergence to formulate the $\text{lower asymptotic divergence}$ $\text{div}(S||\alpha )$ of a probability measure $\alpha$ on $\Sigma$ from a sequence $S$ over $\Sigma$ and the $\text{upper asymptotic divergence}$ $\text{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 $\text{Div}(S||\alpha )=0$. We also use the Kullback-Leibler divergence to quantify the $\text{total risk }$ ${\text{Risk}}_G(w)$ that a finite-state gambler $G$ takes when betting along a prefix $w$ of $S$. Our main theorem is a $\text{strong dichotomy theorem}$ that uses the above notions to $\text{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 $\alpha$-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 is $2^{\text{Div}(S||\alpha )|w|}$. (2) The exponential rate of loss is $2^{-{\text{Risk}}_G(w)}$. We also use (1) to show that $1-\text{Div}(S||\alpha )/c$, where $c=\log (1/{\min }_{a\in \Sigma }\alpha (a))$, is an upper bound on the finite-state $\alpha$-dimension of $S$ and prove the dual fact that $1-\text{div}(S||\alpha )/c$ is an upper bound on the finite-state strong $\alpha$-dimension of $S$.