A divergence formula for randomness and dimension

DOI10.1016/J.TCS.2010.09.005zbMath1259.28007OpenAlexW2068594522MaRDI QIDQ616503

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

Kolmogorov complexityKullback-Leibler divergenceShannon entropyrandomnessfinite-state dimensionconstructive dimension

Mathematics Subject Classification ID

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

Related Items (3)

Mutual dimension and random sequences ⋮ Dimension spectra of random subfractals of self-similar fractals ⋮ Dimension and the structure of complexity classes

Cites Work

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

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