A divergence formula for randomness and dimension

AbstractIf 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 formuladimβ(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 dimFSβ(R) and DimFSβ(R). In the course of proving this, we also prove finite-state compression characterizations of dimFSβ(S) and DimFSβ(S)