A divergence formula for randomness and dimension

DOI10.1016/J.TCS.2010.09.005MaRDI QIDQ616503zbMATH OpenOpenAlexFDO

Authors Jack H. Lutz

Publication date 10 January 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.09.005

zbMATH Keywords

constructive dimensionfinite-state dimensionKolmogorov complexityKullback-Leibler divergencerandomnessShannon entropy

Mathematics Subject Classification ID

Spaces of measures, convergence of measures (28A33) Hausdorff and packing measures (28A78) Fractals (28A80) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Measures of information, entropy (94A17)

Review text

The reviewer considers the first part of the author's abstract as most illustrative of the content of the paper. ``If \(S\) is an infinite sequence over a finite alphabet \(\Sigma\) and \(\beta\) is a probability measure on \(\Sigma\), then the \textit{dimension} of \(S\) with respect to \(\beta\), written \(\mathrm{dim}^\beta(S)\), is a constructive version of the Billingsley dimension that coincides with the (constructive Hausdorff) dimension \(\mathrm{dim}(S)\) when \(\beta\) is the uniform probability measure. This paper shows that \(\mathrm{dim}^\beta(S)\) and its dual \(\mathrm{Dim}^\beta(S)\), the \textit{strong dimension} of \(S\) with respect to \(\beta\), can be used in conjunction with randomness to measure the similarity of two probability measures \(\alpha\) and \(\beta\) on \(\Sigma\). Specifically, we prove that the divergence formula \[ \mathrm{dim}^\beta(R)=\mathrm{Dim}^\beta(R)= \frac{\mathcal H (\alpha)}{\mathcal H (\alpha)+ \mathcal{D}(\alpha\,\|\,\beta)} \] holds whenever \(\alpha\) and \(\beta\) are computable, positive probability measures on \(\Sigma\) and \(R\in \Sigma^\infty\) is random with respect to \(\alpha\). In this formula, \(\mathcal H (\alpha)\) is the Shannon entropy of \(\alpha\), and \(\mathcal D(\alpha\, \|\, \beta)\) is the Kullback-Leibler divergence between \(\alpha\) and \(\beta\).

Recommendations

• A divergence formula for randomness and dimension
• Some general divergence measures for probability distributions
• Randomness Criteria in Terms of $ {\alpha }$-Divergences
• On metric divergences of probability measures
• Dimension formula for random transformations
• Formulation and properties of a divergence used to compare probability measures without absolute continuity
• scientific article; zbMATH DE number 3922519
• A result on diffuse random measure
• A dimensional result for random self-similar sets

Cites work

• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• A Mathematical Theory of Communication
• A unified approach to the definition of random sequences
• An introduction to Kolmogorov complexity and its applications
• Dimension in Complexity Classes
• Dimensions of Points in Self-Similar Fractals
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Elements of Information Theory
• Endliche Automaten und Zufallsfolgen
• Entropy rates and finite-state dimension
• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• Finite-state dimension
• Hausdorff dimension in probability theory. I, II
• The definition of random sequences
• The dimensions of individual strings and sequences
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• Two definitions of fractional dimension

Cited in

(5)

• A divergence formula for randomness and dimension
• Randomness Criteria in Terms of $ {\alpha }$-Divergences
• Dimension spectra of random subfractals of self-similar fractals
• From the divergence between two measures to the shortest path between two observables
• Dimension and the structure of complexity classes

This page was built for publication: A divergence formula for randomness and dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616503)