A Divergence Formula for Randomness and Dimension
Author:
Preprint
Abstract
If $S$ is an infinite sequence over a finite alphabet $\Sigma$ and $\beta$ is a probability measure on $\Sigma$, then the {\it dimension} of $ S$ with respect to $\beta$, written $\dim^\beta(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $\beta$ is the uniform probability measure. This paper shows that $\dim^\beta(S)$ and its dual $\Dim^\beta(S)$, the {\it strong dimension} of $S$ with respect to $\beta$, can be used in conjunction with randomness to measure the similarity of two probability measures $\alpha$ and $\beta$ on $\Sigma$. Specifically, we prove that the {\it divergence formula} \[ \dim^\beta(R) = \Dim^\beta(R) =\frac{\CH(\alpha)}{\CH(\alpha) + \D(\alpha || \beta)} \] holds whenever $\alpha$ and $\beta$ are computable, positive probability measures on $\Sigma$ and $R \in \Sigma^\infty$ is random with respect to $\alpha$. In this formula, $\CH(\alpha)$ is the Shannon entropy of $\alpha$, and $\D(\alpha||\beta)$ is the Kullback-Leibler divergence between $\alpha$ and $\beta$. We also show that the above formula holds for all sequences $R$ that are $\alpha$-normal (in the sense of Borel) when $\dim^\beta(R)$ and $\Dim^\beta(R)$ are replaced by the more effective finite-state dimensions $\dimfs^\beta(R)$ and $\Dimfs^\beta(R)$. In the course of proving this, we also prove finite-state compression characterizations of $\dimfs^\beta(S)$ and $\Dimfs^\beta(S)$.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Entropy rates and finite-state dimensionTheoretical Computer Science, 2005
- Finite-state dimensionTheoretical Computer Science, 2004
- The dimensions of individual strings and sequencesInformation and Computation, 2003
- A Kolmogorov complexity characterization of constructive Hausdorff dimensionInformation Processing Letters, 2002
- Gambling using a finite state machineIEEE Transactions on Information Theory, 1991
- Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groupsActa Mathematica, 1984
- Two definitions of fractional dimensionMathematical Proceedings of the Cambridge Philosophical Society, 1982
- Endliche Automaten und ZufallsfolgenActa Informatica, 1972
- A unified approach to the definition of random sequencesTheory of Computing Systems, 1971
- THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIESThe Quarterly Journal of Mathematics, 1949