2026-08-12T12:12:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11916 2024-03-06T10:49:00Z ddc:004 open_access

Randomness and Initial Segment Complexity for Probability Measures Nies, André Stephan, Frank algorithmic randomness probability measure on Cantor space Kolmogorov complexity statistical superposition quantum states We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure μ on the space of infinite bit sequences is Martin-Löf absolutely continuous if the non-Martin-Löf random bit sequences form a null set with respect to μ. We think of this as a weak randomness notion for measures. We begin with examples, and a robustness property related to Solovay tests. Our main work connects our property to the growth of the initial segment complexity for measures μ; the latter is defined as a μ-average over the complexity of strings of the same length. We show that a maximal growth implies our weak randomness property, but also that both implications of the Levin-Schnorr theorem fail. We briefly discuss K-triviality for measures, which means that the growth of initial segment complexity is as slow as possible. We show that full Martin-Löf randomness of a measure implies Martin-Löf absolute continuity; the converse fails because only the latter property is compatible with having atoms. In a final section we consider weak randomness relative to a general ergodic computable measure. We seek appropriate effective versions of the Shannon-McMillan-Breiman theorem and the Brudno theorem where the bit sequences are replaced by measures. Schloss Dagstuhl – Leibniz-Zentrum für Informatik André Nies and Frank Stephan 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.55 urn:nbn:de:0030-drops-119168 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.55 eng https://creativecommons.org/licenses/by/3.0/legalcode