Jack H. Lutz |

If S is an infinite sequence over a finite alphabet Σ and β
is a probability measure on Σ, then the \it 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 \it 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
\it divergence formula
\[ \dim^β(R) = \Dim^β(R) =\frac\CH(α)\CH(α) + \D(α || β) \] holds whenever α and β are computable, positive probability measures on Σ and R \in Σ^∞ is random with respect to α. In this formula, \CH(α) is the Shannon entropy of α, and \D(α||β) is the Kullback-Leibler divergence between α and β. |

Published: 25th June 2009.

ArXived at: https://dx.doi.org/10.4204/EPTCS.1.14 | bibtex | |

Comments and questions to: eptcs@eptcs.org |

For website issues: webmaster@eptcs.org |