Conditional Kolmogorov Complexity and Universal Probability
| Authors | |
|---|---|
| Publication date | 05-06-2012 |
| Number of pages | 18 |
| Publisher | Ithaca, NY: ArXiv |
| Organisations |
|
| Abstract |
The conditional in conditional Kolmogorov complexity commonly is taken to be a finite binary string. The Coding Theorem of L.A. Levin connects unconditional prefix Kolmogorov complexity with the discrete universal distribution. The least upper semicomputable code-length is up to a constant equal to the negative logarithm of the greatest lower semicomputable probability mass function. We investigate conditional versions of the Coding Theorem for singleton and joint probability distributions under alternative definitions. No conditional Coding Theorem holds in the singleton case, in the joint case under the customary definition of conditional probability, but it does hold in the joint case under an alternative definition.
|
| Document type | Working paper |
| Note | Version 2 (2013) also available on ArXiv.org. |
| Language | English |
| Related publication | Conditional Kolmogorov complexity and universal probability |
| Published at | https://arxiv.org/abs/1206.0983v1 |
| Downloads |
1206.0983v1
(Submitted manuscript)
|
| Permalink to this page | |