A divergence formula for randomness and dimension
A divergence formula for randomness and dimension
复制标题
随机性和维度的散度公式
DOI：
--
复制
发表时间：
2008
影响因子：
1.1
通讯作者：
J. H. Lutz
中科院分区：
文献类型：
--
作者：
J. H. Lutz
如果S是有限字母表Σ上的无限序列，且β是Σ上的概率测度，则S关于β的维度(记为$dim^eTA(S)$)是比林斯利维度的构造性形式，它与当β是一致概率测度时的(构造性Hausdorff)维Dim(S)重合。本文证明了Dimβ(S)及其对偶Dimβ(S)，即S关于β的强维，可以结合随机性来度量两个概率度量*和β在Σ上的相似性。具体地，我们证明了散度公式$${mathrm{dim}}^eta(R)={mathrm{dim}}^eta(R)=frac{{mathcal{H}}(alpha)}{{mathcal{H}}(alpha)+{mathcal{D}}(α||eta)}$$
当*和β是可计算的时，Σ和R*Σ*上的正概率度量关于*是随机的。在这个公式中，${mathcal{H}}(α)$是*的香农熵，${mathcal{D}}(α||eta)$是*和β之间的Kullback-Leibler散度。
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^eta(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 $$ {mathrm {dim}}^eta(R) = {mathrm{Dim}}^eta(R) =frac{{mathcal{H}}(alpha)}{{mathcal{H}}(alpha) + {mathcal{D}}(alpha || eta)} $$
holds whenever *** and β are computable, positive probability measures on Σ and R *** Σ *** is random with respect to *** . In this formula, ${mathcal{H}}(alpha)$ is the Shannon entropy of *** , and ${mathcal{D}}(alpha||eta)$ is the Kullback-Leibler divergence between *** and β .