A divergence formula for randomness and dimension

If SS is an infinite sequence over a finite alphabet ΣΣ and ββ is a probability measure on ΣΣ, then the dimension   of SS 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 SS 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∈Σ∞R∈Σ∞ is random with respect to αα. In this formula, H(α)H(α) is the Shannon entropy of αα, and D(α∥β)D(α∥β) is the Kullback–Leibler divergence between αα and ββ. We also show that the above formula holds for all sequences RR 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).