A divergence formula for randomness and dimension
type: Item
instance of: scholarly article
title: A divergence formula for randomness and dimension
zbMATH Open document ID: 1259.28007
author: Jack H. Lutz
published in: Theoretical Computer Science
publication date: 2011-01-10T00:00:00Z
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\).''
reviewed by: Enrico Zoli
Mathematics Subject Classification ID: 28A78
Mathematics Subject Classification ID: 28A33
Mathematics Subject Classification ID: 28A80
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 94A17
zbMATH DE Number: 5834261
zbMATH Keywords: constructive dimension
zbMATH Keywords: finite-state dimension
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: Kullback-Leibler divergence
zbMATH Keywords: randomness
zbMATH Keywords: Shannon entropy
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.09.005
OpenAlex ID: W2068594522
cites work: Effective Strong Dimension in Algorithmic Information and Computational Complexity
cites work: Hausdorff dimension in probability theory. I, II
cites work: Entropy rates and finite-state dimension
cites work: Elements of Information Theory
cites work: Finite-state dimension
cites work: THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
cites work: An introduction to Kolmogorov complexity and its applications
cites work: Dimension in Complexity Classes
cites work: The dimensions of individual strings and sequences
cites work: Dimensions of Points in Self-Similar Fractals
cites work: The definition of random sequences
cites work: A Kolmogorov complexity characterization of constructive Hausdorff dimension.
cites work: A unified approach to the definition of random sequences
cites work: Endliche Automaten und Zufallsfolgen
cites work: A Mathematical Theory of Communication
cites work: Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
cites work: Two definitions of fractional dimension
DOI: 10.1016/J.TCS.2010.09.005
Recommended article: A Divergence Formula for Randomness and Dimension
Recommended article: Some general divergence measures for probability distributions
Recommended article: Randomness Criteria in Terms of $ {\alpha }$-Divergences
Recommended article: Q3552460
Recommended article: Dimension formula for random transformations
Recommended article: Formulation and properties of a divergence used to compare probability measures without absolute continuity
Recommended article: Q3698689
Recommended article: A result on diffuse random measure
Recommended article: A dimensional result for random self-similar sets
description: scientific article; zbMATH DE number 5834261