Algorithmic tests and randomness with respect to a class of measures

Laurent Bienvenu; Peter Gacs; Mathieu Hoyrup; Cristobal Rojas; Alexander Shen

hal-00644785, version 1

Algorithmic tests and randomness with respect to a class of measures

Laurent Bienvenu ()^a^, 1, Peter Gacs ()^b^, 2, Mathieu Hoyrup () ³, Cristobal Rojas ()^c^, 4, Alexander Shen (, ) ⁵

Proceedings of the Steklov Institute of Mathematics 274, 1 (2011) 34-89

a – CNRS
b – Boston University
c – Universidad Andrés Bello
1 : Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA)
http://www.liafa.jussieu.fr/
CNRS : UMR7089 – Université Paris VII - Paris Diderot 2, place Jussieu, Case 7014, 75251 Paris Cedex 05 - Tél: +33(0)1.44.27.68.45 - Fax: +33(0)1.44.27.68.49 France
2 : Computer Science Department [Boston] (Boston University)
http://www.cs.bu.edu/
Boston University Department of Computer Science Boston University 111 Cummington St, Room 138 Boston, MA 02215 États-Unis
3 : CARTE (INRIA Nancy - Grand Est / LORIA)
CNRS : UMR7503 – INRIA – Université de Lorraine France
4 : Department of Mathematics - University of Toronto
http://www.math.toronto.edu/
University of Toronto Department of Mathematics - University of Toronto - Bahen Centre - 40 St. George St. - Toronto, Ontario - CANADA - M5S 2E4 Canada
5 : Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
http://www.lirmm.fr
CNRS : UMR5506 – Université Montpellier II - Sciences et techniques CC 477, 161 rue Ada, 34095 Montpellier Cedex 5 France

Références bibliographiques

Liste des fichiers attachés à ce document :

PDF

classes.pdf

(530.9 KB)

hal-00644785, version 1
http://hal.inria.fr/hal-00644785
oai:hal.inria.fr:hal-00644785
Contributeur : Mathieu Hoyrup <>
Soumis le : Vendredi 25 Novembre 2011, 11:32:09
Dernière modification le : Vendredi 21 Septembre 2012, 13:55:41

Voir la fiche concise

Documents associés

PDF :

DOI : 10.1134/S0081543811060058

Texte intégral chez l'éditeur

Voir aussi

Exporter

Bibtex EndNote TEI RefWorks

%% hal-00644785, version 1
%% http://hal.inria.fr/hal-00644785
@article{bienvenu:hal-00644785,
    hal_id = {hal-00644785},
    url = {http://hal.inria.fr/hal-00644785},
    title = {{Algorithmic tests and randomness with respect to a class of measures}},
    author = {Bienvenu, Laurent and Gacs, Peter and Hoyrup, Mathieu and Rojas, Cristobal and Shen, Alexander},
    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{\"o}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.}},
    language = {Anglais},
    affiliation = {Laboratoire d'informatique Algorithmique : Fondements et Applications - LIAFA , Computer Science Department [Boston] - Boston University , CARTE - INRIA Nancy - Grand Est / LORIA , Department of Mathematics - University of Toronto , Laboratoire d'Informatique de Robotique et de Micro{\'e}lectronique de Montpellier - LIRMM},
    publisher = {Steklov Institute of Mathematics},
    pages = {34-89},
    journal = {Proceedings of the Steklov Institute of Mathematics},
    volume = {274},
    number = {1 },
    audience = {internationale },
    doi = {10.1134/S0081543811060058 },
    year = {2011},
    month = Nov,
    pdf = {http://hal.inria.fr/hal-00644785/PDF/classes.pdf},
}

%F hal-00644785, version 1
%0 Journal Article
%U http://hal.inria.fr/hal-00644785
%2 MATH:MATH_PR;INFO:INFO_IT;MATH:MATH_IT
%T Algorithmic tests and randomness with respect to a class of measures
%A Bienvenu, Laurent
%A Gacs, Peter
%A Hoyrup, Mathieu
%A Rojas, Cristobal
%A Shen, Alexander
%+ Laboratoire d'informatique Algorithmique : Fondements et Applications - LIAFA , Computer Science Department [Boston] - Boston University , CARTE - INRIA Nancy - Grand Est / LORIA , Department of Mathematics - University of Toronto , Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
%Z INFO/ESCAPE
%X 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.
%2 F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.0: Computability theory, F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.2: Computability theory
%G Anglais
%J Proceedings of the Steklov Institute of Mathematics
%8 2011-11-25
%2 internationale
%I Steklov Institute of Mathematics
%V 274
%N 1
%P 34-89
%R 10.1134/S0081543811060058
%2 http://www.springerlink.com/content/x5w44l14417m5642/
%2 http://arxiv.org/abs/1103.1529

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="hal-00644785"><analytic>
<author><persName><forename>Laurent</forename><surname>Bienvenu</surname></persName>
<affiliation>
<orgName type="laboratory">LIAFA</orgName>
<orgName type="team">Laboratoire d'informatique Algorithmique : Fondements et Applications</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7089</orgName>
<orgName type="institution">Université Paris VII - Paris Diderot</orgName>
</affiliation>
</author>
<author><persName><forename>Peter</forename><surname>Gacs</surname></persName>
<affiliation>
<orgName type="laboratory">Boston University</orgName>
<orgName type="team">Computer Science Department [Boston]</orgName>
<country>US</country>
<orgName type="institution">Boston University</orgName>
</affiliation>
</author>
<author><persName><forename>Mathieu</forename><surname>Hoyrup</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Nancy - Grand Est / LORIA</orgName>
<orgName type="team">CARTE</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Cristobal</forename><surname>Rojas</surname></persName>
<affiliation>
<orgName type="team">Department of Mathematics - University of Toronto</orgName>
<country>CA</country>
<orgName type="institution">University of Toronto</orgName>
</affiliation>
</author>
<author><persName><forename>Alexander</forename><surname>Shen</surname></persName>
<affiliation>
<orgName type="laboratory">LIRMM</orgName>
<orgName type="team">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5506</orgName>
<orgName type="institution">Université Montpellier II - Sciences et techniques</orgName>
</affiliation>
</author>
<title type="main" level="a">Algorithmic tests and randomness with respect to a class of measures</title></analytic><monogr><title level="j" type="main">Proceedings of the Steklov Institute of Mathematics</title><imprint><publisher>Steklov Institute of Mathematics</publisher><biblScope type="publicationDate">2011-11-25</biblScope><biblScope type="vol">274</biblScope><biblScope type="issue">1</biblScope><biblScope type="pp">34-89</biblScope></imprint></monogr><idno type="doi">10.1134/S0081543811060058</idno><idno type="HALid">http://hal.inria.fr/hal-00644785</idno><idno type="HALFile">http://hal.inria.fr/hal-00644785/PDF/classes.pdf</idno></biblStruct>
</listBibl>
</listBibl>

Proceedings of the Steklov Institute of Mathematics
Publisher	MAIK Nauka/Interperiodica (МАИК Наука/Интерпериодика)
ISSN	0081-5438 (eISSN : 1531-8605)