Algorithmic tests and randomness with respect to a class of measures

Abstract : This paper offers some new results on randomness with respect to classes of measures, along with a didactical exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure Bp. A notion of "uniform test" for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures Bp have the important property that p can be recovered from each random sequence of Bp. The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.
Type de document :
Article dans une revue
Proceedings of the Steklov Institute of Mathematics, MAIK Nauka/Interperiodica, 2011, 274 (1), pp.34-89. 〈http://www.springerlink.com/content/x5w44l14417m5642/〉. 〈10.1134/S0081543811060058〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00644785
Contributeur : Mathieu Hoyrup <>
Soumis le : vendredi 25 novembre 2011 - 11:32:09
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 12:00:47

Fichier

classes.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Laurent Bienvenu, Peter Gacs, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen. Algorithmic tests and randomness with respect to a class of measures. Proceedings of the Steklov Institute of Mathematics, MAIK Nauka/Interperiodica, 2011, 274 (1), pp.34-89. 〈http://www.springerlink.com/content/x5w44l14417m5642/〉. 〈10.1134/S0081543811060058〉. 〈hal-00644785〉

Partager

Métriques

Consultations de la notice

384

Téléchargements de fichiers

109