文章基本信息
- 标题：A Divergence Formula for Randomness and Dimension (Short Version)
- 本地全文：下载
- 作者：Jack H. Lutz
- 期刊名称：Electronic Proceedings in Theoretical Computer Science
- 电子版ISSN：2075-2180
- 出版年度：2008
- 卷号：1
- 页码：149-152
- DOI：10.4204/EPTCS.1.14
- 出版社：Open Publishing Association
- 摘要：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 Σ^\infty is random with respect to α. In this formula, \CH(α) is the Shannon entropy of α, and \D(α||β) is the Kullback-Leibler divergence between α and β.
