Geodesic
Algorithmic tests and randomness with respect to a~class of measures
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 41-102.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{TM_2011_274_a4,
     author = {Laurent Bienvenu and Peter G\'acs and Mathieu Hoyrup and Cristobal Rojas and Alexander Shen},
     title = {Algorithmic tests and randomness with respect to a~class of measures},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {41--102},
     publisher = {mathdoc},
     volume = {274},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2011_274_a4/}
}
TY  - JOUR
AU  - Laurent Bienvenu
AU  - Peter Gács
AU  - Mathieu Hoyrup
AU  - Cristobal Rojas
AU  - Alexander Shen
TI  - Algorithmic tests and randomness with respect to a~class of measures
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2011
SP  - 41
EP  - 102
VL  - 274
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2011_274_a4/
LA  - ru
ID  - TM_2011_274_a4
ER  - 
%0 Journal Article
%A Laurent Bienvenu
%A Peter Gács
%A Mathieu Hoyrup
%A Cristobal Rojas
%A Alexander Shen
%T Algorithmic tests and randomness with respect to a~class of measures
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2011
%P 41-102
%V 274
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2011_274_a4/
%G ru
%F TM_2011_274_a4
Laurent Bienvenu; Peter Gács; Mathieu Hoyrup; Cristobal Rojas; Alexander Shen. Algorithmic tests and randomness with respect to a~class of measures. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 41-102. http://geodesic.mathdoc.fr/item/TM_2011_274_a4/

[1] Avigad J., Gerhardy P., Towsner H., “Local stability of ergodic averages”, Trans. Amer. Math. Soc., 362:1 (2010), 261–288 | DOI | MR | Zbl

[2] Bienvenu L., Day A., Hoyrup M., Mezhirov I., Shen A., A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points, E-print, 2010, arXiv: 1007.5249 [math.DS]

[3] Bienvenu L., Romashchenko A., Shen A., “Sparse sets”, Journées automates cellulaires, Proc. First Symp. on Cellular Automata, Uzès (France), 2008, 18–28 http://hal.archives-ouvertes.fr/docs/00/27/40/10/PDF/18-28.pdf

[4] Chaitin G.J., “A theory of program size formally identical to information theory”, J. ACM, 22 (1975), 329–340 | DOI | MR | Zbl

[5] Chernov A., Shen A., Vereshchagin N., Vovk V., “On-line probability, complexity and randomness”, Algorithmic learning theory, Proc. 19th Intern. Conf., Budapest, 2008, Lect. Notes Comput. Sci., 5254, eds. Y. Freund, L. Györfi, G. Turán, T. Zeugmann, Springer, Berlin, 2008, 138–153 | DOI | MR | Zbl

[6] Day A.R., Miller J.S., “Randomness for non-computable measures”, Trans. Amer. Math. Soc. (to appear) http://www.math.wisc.edu/~jmiller/Papers/neutral.pdf | MR

[7] Gács P., Lecture notes on descriptional complexity and randomness, Tech. Rep., Boston Univ., Comput. Sci. Dept., Boston, MA, 1988 http://www.cs.bu.edu/~gacs/papers/ait-notes.pdf

[8] Gács P., Komplexität und Zufälligkeit, PhD Thesis, J.W. Goethe Univ., Frankfurt, 1978 | Zbl

[9] Gács P., “Exact expressions for some randomness tests”, Ztschr. Math. Logik und Grundlagen Math., 26 (1980), 385–394 ; Theoretical Computer Science, Proc. 4th GI Conf., Lect. Notes Comput. Sci., 67, Springer, Berlin, 1979, 124–131 | DOI | MR | Zbl | DOI | MR

[10] Gács P., “On the relation between descriptional complexity and algorithmic probability”, Theor. Comput. Sci., 22 (1983), 71–93 ; Proc. 22nd Annu. Symp. on Foundations of Computer Science, Nashville, 1981, IEEE Comput. Soc., New York, 1981, 296–303 | DOI | MR | Zbl

[11] Gács P., “Uniform test of algorithmic randomness over a general space”, Theor. Comput. Sci., 341:1–3 (2005), 91–137 | DOI | MR | Zbl

[12] Hoyrup M., Rojas C., “An application of Martin-Löf randomness to effective probability theory”, Mathematical theory and computational practice, Proc. Conf. CiE 2009, Lect. Notes Comput. Sci., 5635, Springer, Berlin, 2009, 260–269 | DOI | MR | Zbl

[13] Hoyrup M., Rojas C., “Computability of probability measures and Martin-Löf randomness over metric spaces”, Inf. and Comput., 207:7 (2009), 830–847 | DOI | MR | Zbl

[14] Kolmogorov A.N., “K logicheskim osnovam teorii informatsii i teorii veroyatnostei”, Probl. peredachi inform., 5:3 (1969), 3–7 ; Kolmogorov A.N., “Logical basis for information theory and probability theory”, IEEE Trans. Inf. Theory, 14:5 (1968), 662–664 | MR | Zbl | DOI | MR | Zbl

[15] Kuratowski K., Topology, V. 1, 2., Acad. Press, New York, 1966, 1968 ; Куратовский К., Топология, Т. 1, 2., Мир, М., 1966, 1969 | MR | Zbl

[16] Levin L.A., “O ponyatii sluchainoi posledovatelnosti”, DAN SSSR, 212:3 (1973), 548–550 | Zbl

[17] Levin L.A., “Ravnomernye testy sluchainosti”, DAN SSSR, 227:1 (1976), 33–35 | MR | Zbl

[18] Levin L.A., “Randomness conservation inequalities: Information and independence in mathematical theories”, Inf. and Control., 61:1 (1984), 15–37 | DOI | MR | Zbl

[19] Li M., Vitányi P., An introduction to Kolmogorov complexity and its applications, 3rd ed., Springer, New York, 2008 | MR | Zbl

[20] Martin-Löf P., “The definition of random sequences”, Inf. and Control., 9 (1966), 602–619 | DOI | MR | Zbl

[21] Medvedev Yu.T., “Stepeni trudnosti massovykh problem”, DAN SSSR, 104:4 (1955), 501–504 | MR | Zbl

[22] Miller J.S., “Degrees of unsolvability of continuous functions”, J. Symb. Log., 69:2 (2004), 555–584 | DOI | MR | Zbl

[23] Schnorr C.P., “Process complexity and effective random tests”, J. Comput. Syst. Sci., 7:4 (1973), 376–388 ; Proc. 4th Annu. ACM Symp. on Theory of Computing, Denver, 1972, ACM, New York, 1972, 168–176 | DOI | MR | Zbl | Zbl

[24] Shafer G., Shen A., Vereshchagin N., Vovk V., Test martingales, Bayes factors, and $p$-values, E-print, 2009, arXiv: 0912.4269v2 [math.ST] | MR

[25] Shafer G., Vovk V., Probability and finance: It's only a game!, Wiley, Chichester, 2001 | MR | Zbl

[26] Shen A., Algorithmic information theory and Kolmogorov complexity, Tech. Rep. 2000-034, Uppsala Univ., Uppsala, 2000 http://www.it.uu.se/research/publications/reports/2000-034/

[27] Vovk V., Shen A., “Prequential randomness and probability”, Theor. Comput. Sci., 411:29–30 (2010), 2632–2646 | DOI | MR | Zbl

[28] Strassen V., “The existence of probability measures with given marginals”, Ann. Math. Stat., 36 (1965), 423–439 | DOI | MR | Zbl

[29] V'yugin V.V., “Ergodic theorems for individual random sequences”, Theor. Comput. Sci., 207:2 (1998), 343–361 | DOI | MR | Zbl

[30] Zvonkin A.K., Levin L.A., “Slozhnost konechnykh ob'ektov i obosnovanie ponyatii informatsii i sluchainosti s pomoschyu teorii algoritmov”, UMN., 25:6 (1970), 85–127 | MR | Zbl