A divergence formula for randomness and dimension

• Published in: Theoretical computer science 2011, Vol.412 (1), p.166-177
• Main Author: Lutz, Jack H.
• Format: Article
• Language: English
• Subjects: C (programming language); Compressing; Construction; Constructive dimension; Dimensional measurements; Divergence; Entropy; Finite-state dimension; Kolmogorov complexity; Kullback–Leibler divergence; Mathematical analysis; Randomness; Shannon entropy; Similarity
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2010.09.005

If S is an infinite sequence over a finite alphabet Σ and β is a probability measure on Σ , then the dimension of S with respect to β , written dim β ( S ) , is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension dim ( S ) when β is the uniform probability measure. This paper shows that dim β ( S ) and its dual Dim β ( S ) , the strong dimension of S with respect to β , can be used in conjunction with randomness to measure the similarity of two probability measures α and β on Σ . Specifically, we prove that the divergence formula dim β ( R ) = Dim β ( R ) = H ( α ) H ( α ) + D ( α ∥ β ) holds whenever α and β are computable, positive probability measures on Σ and R ∈ Σ ∞ is random with respect to α . In this formula, H ( α ) is the Shannon entropy of α , and D ( α ∥ β ) is the Kullback–Leibler divergence between α and β . We also show that the above formula holds for all sequences R that are α -normal (in the sense of Borel) when dim β ( R ) and Dim β ( R ) are replaced by the more effective finite-state dimensions dim FS β ( R ) and Dim FS β ( R ) . In the course of proving this, we also prove finite-state compression characterizations of dim FS β ( S ) and Dim FS β ( S ) .