General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Trudy MIAN:

Personal entry:
Save password
Forgotten password?

Tr. Mat. Inst. Steklova, 2011, Volume 274, Pages 41–102 (Mi tm3322)  

This article is cited in 14 scientific papers (total in 14 papers)

Algorithmic tests and randomness with respect to a class of measures

Laurent Bienvenua, Peter Gácsb, Mathieu Hoyrupc, Cristobal Rojasd, Alexander Shenef

a Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA), CNRS UMR 7089 & Université Paris Diderot, Paris Cedex, France
b Department of Computer Science, Boston University, Boston, MA, USA
c Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Vandœuvre-lés-Nancy, France
d Department of Mathematics, University of Toronto, Toronto, Ontario, Canada
e Laboratoire d'Informatique Fondamentale de Marseille (LIF), Université Aix–Marseille, CNRS UMR 6166, Marseille Cedex, France
f Institute for Information Transmission Problems (Kharkevich Institute), Russian Academy of Sciences, Moscow, Russia

Abstract: This paper offers some new results on randomness with respect to classes of measures, along with a didactic 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 $B_p$. 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 $B_p$ have the important property that $p$ can be recovered from each random sequence of $B_p$. 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.

Full text: PDF file (561 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics, 2011, 274, 34–89

Bibliographic databases:

UDC: 510.5
Received in March 2011

Citation: Laurent Bienvenu, Peter Gács, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen, “Algorithmic tests and randomness with respect to a class of measures”, Algorithmic aspects of algebra and logic, Collected papers. Dedicated to Academician Sergei Ivanovich Adian on the occasion of his 80th birthday, Tr. Mat. Inst. Steklova, 274, MAIK Nauka/Interperiodica, Moscow, 2011, 41–102; Proc. Steklov Inst. Math., 274 (2011), 34–89

Citation in format AMSBIB
\by Laurent~Bienvenu, Peter~G\'acs, Mathieu~Hoyrup, Cristobal~Rojas, Alexander~Shen
\paper Algorithmic tests and randomness with respect to a~class of measures
\inbook Algorithmic aspects of algebra and logic
\bookinfo Collected papers. Dedicated to Academician Sergei Ivanovich Adian on the occasion of his 80th birthday
\serial Tr. Mat. Inst. Steklova
\yr 2011
\vol 274
\pages 41--102
\publ MAIK Nauka/Interperiodica
\publaddr Moscow
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 274
\pages 34--89

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Bienvenu L., Monin B., “Von Neumann's Biased Coin Revisited”, 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science (Lics), IEEE Symposium on Logic in Computer Science, IEEE, 2012, 145–154  crossref  mathscinet  zmath  isi
    2. Bienvenu L., Romashchenko A., Shen A., Taveneaux A., Vermeeren S., “The Axiomatic Power of Kolmogorov Complexity”, Ann. Pure Appl. Log., 165:9, SI (2014), 1380–1402  crossref  mathscinet  zmath  isi  elib
    3. Weihrauch K., Tavana N.R., “Representations of Measurable Sets in Computable Measure Theory”, Log. Meth. Comput. Sci., 10:3 (2014), 7  crossref  mathscinet  zmath  isi  elib
    4. Bauwens B., “Prefix and Plain Kolmogorov Complexity Characterizations of 2-Randomness: Simple Proofs”, Arch. Math. Log., 54:5-6 (2015), 615–629  crossref  mathscinet  zmath  isi  elib
    5. Rute J., “Computable randomness and betting for computable probability spaces”, Math. Log. Q., 62:4-5 (2016), 335–366  crossref  mathscinet  zmath  isi  elib  scopus
    6. Rute J., When does randomness come from randomness?, Theor. Comput. Sci., 635 (2016), 35–50  crossref  mathscinet  zmath  isi  elib  scopus
    7. Andreev M., Kumok A., “The Sum $2^{ KM(x)-K(x)}$ Over All Prefixes $x$ of Some Binary Sequence Can be Infinite”, Theor. Comput. Syst., 58:3, SI (2016), 424–440  crossref  mathscinet  zmath  isi  elib  scopus
    8. Bauwens B., “Relating and Contrasting Plain and Prefix Kolmogorov Complexity”, Theor. Comput. Syst., 58:3, SI (2016), 482–501  crossref  mathscinet  zmath  isi  elib  scopus
    9. Bauwens B., Shen A., Takahashi H., “Conditional Probabilities and Van Lambalgen'S Theorem Revisited”, Theor. Comput. Syst., 61:4, SI (2017), 1315–1336  crossref  mathscinet  zmath  isi
    10. Bienvenu L., Hoyrup M., Shen A., “Layerwise Computability and Image Randomness”, Theor. Comput. Syst., 61:4, SI (2017), 1353–1375  crossref  mathscinet  zmath  isi
    11. Vereshchagin N., Shen A., “Algorithmic Statistics: Forty Years Later”, Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60Th Birthday, Lecture Notes in Computer Science, 10010, eds. Day A., Fellows M., Greenberg N., Khoussainov B., Melnikov A., Rosamond F., Springer International Publishing Ag, 2017, 669–737  crossref  mathscinet  zmath  isi
    12. Novikov G., “Randomness Deficiencies”, Unveiling Dynamics and Complexity, Cie 2017, Lecture Notes in Computer Science, 10307, eds. Kari J., Manea F., Petre I., Springer International Publishing Ag, 2017, 338–350  crossref  mathscinet  zmath  isi  scopus
    13. Rute J., “Schnorr Randomness For Noncomputable Measures”, Inf. Comput., 258 (2018), 50–78  crossref  mathscinet  zmath  isi
    14. Bienvenu L., Figueira S., Monin B., Shen A., “Algorithmic Identification of Probabilities Is Hard”, J. Comput. Syst. Sci., 95 (2018), 98–108  crossref  mathscinet  zmath  isi
  • Труды Математического института им. В. А. Стеклова Proceedings of the Steklov Institute of Mathematics
    Number of views:
    This page:522
    Full text:27

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019