Conditional Kolmogorov complexity and universal probability

DOI10.1016/J.TCS.2013.07.009MaRDI QIDQ391323zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Paul M. B. Vitányi

Publication date 10 January 2014

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

Full work available at URL https://arxiv.org/abs/1206.0983

zbMATH Keywords

coding theorem for conditional versionsconditional Kolmogorov complexityconditional universal probabilitydefinitions of conditional probability

Mathematics Subject Classification ID

Axioms; other general questions in probability (60A05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: The Coding Theorem of L.A. Levin connects unconditional prefix Kolmogorov complexity with the discrete universal distribution. There are conditional versions referred to in several publications but as yet there exist no written proofs in English. Here we provide those proofs. They use a different definition than the standard one for the conditional version of the discrete universal distribution. Under the classic definition of conditional probability, there is no conditional version of the Coding Theorem.

Recommendations

• Proofs of conservation inequalities for Levin's notion of mutual information of 1974
• The Kolmogorov complexity, universal distribution, and coding theorem for generalized length functions
• Logical operations and Kolmogorov complexity

Cites work

• A Mathematical Theory of Communication
• An introduction to Kolmogorov complexity and its applications
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 3492569 (Why is no real title available?)
• scientific article; zbMATH DE number 3557755 (Why is no real title available?)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(9)

• The proof of Levin's conjecture
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Conditional probabilities and van Lambalgen's theorem revisited
• Axiomatizing Kolmogorov complexity
• Towards an axiomatic system for Kolmogorov complexity
• Prefix-free and prefix-correct complexities with compound conditions
• The Kolmogorov complexity, universal distribution, and coding theorem for generalized length functions
• On the computability of conditional probability
• Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)

This page was built for publication: Conditional Kolmogorov complexity and universal probability

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