|
Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2011, Volume 274, Pages 41–102
(Mi tm3322)
|
|
|
|
This article is cited in 25 scientific papers (total in 25 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), Vanduvre-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.
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, Trudy Mat. Inst. Steklova, 274, MAIK Nauka/Interperiodica, Moscow, 2011, 41–102; Proc. Steklov Inst. Math., 274 (2011), 34–89
Linking options:
https://www.mathnet.ru/eng/tm3322 https://www.mathnet.ru/eng/tm/v274/p41
|
|