Abstract
We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure μ on the space of infinite bit sequences is MartinLöf absolutely continuous if the nonMartinLö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 LevinSchnorr theorem fail. We briefly discuss Ktriviality for measures, which means that the growth of initial segment complexity is as slow as possible. We show that full MartinLöf randomness of a measure implies MartinLö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 ShannonMcMillanBreiman theorem and the Brudno theorem where the bit sequences are replaced by measures.
BibTeX  Entry
@InProceedings{nies_et_al:LIPIcs:2020:11916,
author = {Andr{\'e} Nies and Frank Stephan},
title = {{Randomness and Initial Segment Complexity for Probability Measures}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {55:155:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11916},
URN = {urn:nbn:de:0030drops119168},
doi = {10.4230/LIPIcs.STACS.2020.55},
annote = {Keywords: algorithmic randomness, probability measure on Cantor space, Kolmogorov complexity, statistical superposition, quantum states}
}
Keywords: 

algorithmic randomness, probability measure on Cantor space, Kolmogorov complexity, statistical superposition, quantum states 
Collection: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) 
Issue Date: 

2020 
Date of publication: 

04.03.2020 