























The Schnorr-Stimm dichotomy theorem concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet $Σ$. In this paper we use the Kullback-Leibler divergence to formulate the $\textit{lower asymptotic divergence}$ $\text{div}(S||α)$ of a probability measure $α$ on $Σ$ from a sequence $S$ over $Σ$ and the $\textit{upper asymptotic divergence}$ $\text{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 $\text{Div}(S||α)=0$. We also use the Kullback-Leibler divergence to quantify the $\textit{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 $\textit{strong dichotomy theorem}$ that uses the above notions to $\textit{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 is $2^{\text{Div}(S||α)|w|}$. (2) The exponential rate of loss is $2^{-\text{Risk}_G(w)}$. We also use (1) to show that $1-\text{Div}(S||α)/c$, where $c= \log(1/ \min_{a\inΣ}α(a))$, is an upper bound on the finite-state $α$-dimension of $S$ and prove the dual fact that $1-\text{div}(S||α)/c$ is an upper bound on the finite-state strong $α$-dimension of $S$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。