×

zbMATH — the first resource for mathematics

Computable randomness and betting for computable probability spaces. (English) Zbl 1364.03064
Author’s abstract: Unlike Martin-Löf randomness and Schnorr randomness, computable randomness has not been defined, except for a few ad hoc cases, outside of Cantor space. This paper offers such a definition (actually, several equivalent definitions), and further, provides a general method for abstracting “bit-wise” definitions of randomness from Cantor space to arbitrary computable probability spaces. This same method is also applied to give machine characterizations of computable and Schnorr randomness for computable probability spaces, extending the previously known results. The paper contains a new type of randomness – endomorphism randomness – which the author hopes will shed light on the open question of whether Kolmogorov-Loveland randomness is equivalent to Martin-Löf randomness. The last section contains ideas for future research.

MSC:
03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
60A99 Foundations of probability theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Avigad, Uniform distribution and algorithmic randomness, J. Symb. Log. 78 (1) pp 334– (2013) · Zbl 1275.03133 · doi:10.2178/jsl.7801230
[2] L. M. Axon Algorithmically Random Closed Sets and Probability University of Notre Dame 2010
[3] Barmpalias, Algorithmic randomness of closed sets, J. Log. Comput. 17 (6) pp 1041– (2007) · Zbl 1155.03031 · doi:10.1093/logcom/exm033
[4] Bienvenu, Algorithmic tests and randomness with respect to a class of measures, Proc. Steklov Inst. Math. 274 pp 41– (2011) · Zbl 1294.03032 · doi:10.1134/S0081543811060058
[5] Bienvenu, Separations of non-monotonic randomness notions, J. Log. Comput. 22 (4) pp 701– (2012) · Zbl 1316.03021 · doi:10.1093/logcom/exq037
[6] Bienvenu, Constructive equivalence relations on computable probability measures, Ann. Pure Appl. Log. 160 (3) pp 238– (2009) · Zbl 1201.03028 · doi:10.1016/j.apal.2009.01.002
[7] Bienvenu, Strong reductions in effective randomness, Theor. Comput. Sci. 459 pp 55– (2012) · Zbl 1283.68170 · doi:10.1016/j.tcs.2012.06.031
[8] Bienvenu, On the history of martingales in the study of randomness, J. Électron. Hist. Probab. Stat. 5 (1) pp 40– (2009) · Zbl 1170.01366
[9] Bishop, Constructive Analysis, Grundlehren der Mathematischen Wissenschaften Vol. 279 (1985) · Zbl 0656.03042
[10] Bosserhoff, Notions of probabilistic computability on represented spaces, J. Univ. Comput. Sci. 14 (6) pp 956– (2008) · Zbl 1227.03058
[11] V. Brattka Computable versions of Baire’s category theorem, In: Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001, Marianske Lazne, Czech Republic, August 27-31, 2001 Proceedings J. Sgall A. Pultr P. Kolman Lecture Notes in Computer Science Vol. 2136 Springer-Verlag 2001 · Zbl 0999.03057
[12] Brattka, New Computational Paradigms. Changing conceptions of what is computable (2008)
[13] Brattka, Randomness and differentiability, Trans. Amer. Math. Soc. 368 (1) pp 581– (2016) · Zbl 1402.03062 · doi:10.1090/tran/6484
[14] Downey, On Schnorr and computable randomness, martingales, and machines, Math. Log. Q. 50 (6) pp 613– (2004) · Zbl 1062.68064 · doi:10.1002/malq.200310121
[15] Downey, Algorithmic Randomness and Complexity, Theory and Applications of Computability (2010) · Zbl 1221.68005 · doi:10.1007/978-0-387-68441-3
[16] Freer, Computable de Finetti measures, Ann. Pure Appl. Log. 163 (5) pp 530– (2012) · Zbl 1247.03098 · doi:10.1016/j.apal.2011.06.011
[17] Gács, Exact expressions for some randomness tests, Z. Math. Log. Grundlag. Math. 26 (5) pp 385– (1980) · Zbl 0464.60004 · doi:10.1002/malq.19800262502
[18] Gács, Uniform test of algorithmic randomness over a general space, Theor. Comput. Sci. 341 (1-3) pp 91– (2005) · Zbl 1077.68038 · doi:10.1016/j.tcs.2005.03.054
[19] Gács, Randomness on computable probability spaces-a dynamical point of view, Theor. Comput. Syst. 48 (3) pp 465– (2011) · Zbl 1238.68069 · doi:10.1007/s00224-010-9263-x
[20] Hemmerling, Effective metric spaces and representations of the reals, Theor. Comput. Sci. 284 (2) pp 347– (2002) · Zbl 1042.68106 · doi:10.1016/S0304-3975(01)00093-7
[21] Hertling, Invariance properties of random sequences, J. Univers. Comput. Sci. 3 (11) pp 1241– (1997) · Zbl 0969.60002
[22] Hertling, Random elements in effective topological spaces with measure, Inform. Comput. 181 (1) pp 32– (2003) · Zbl 1055.68059 · doi:10.1016/S0890-5401(02)00034-2
[23] Hitchcock, Why computational complexity requires stricter martingales, Theor. Comput. Syst. 39 (2) pp 277– (2006) · Zbl 1103.68057 · doi:10.1007/s00224-005-1135-4
[24] Hoyrup, Computability of probability measures and Martin-Löf randomness over metric spaces, Inform. Comput. 207 (7) pp 830– (2009) · Zbl 1167.68023 · doi:10.1016/j.ic.2008.12.009
[25] Kastermans, Comparing notions of randomness, Theor. Comput. Sci. 411 (3) pp 602– (2010) · Zbl 1184.68274 · doi:10.1016/j.tcs.2009.09.036
[26] Kjos-Hanssen, Effective dimension of points visited by Brownian motion, Theor. Comput. Sci. 410 (4-5) pp 347– (2009) · Zbl 1158.68017 · doi:10.1016/j.tcs.2008.09.045
[27] Levin, Uniform tests for randomness, Dokl. Akad. Nauk SSSR 227 (1) pp 33– (1976) · Zbl 0341.94013
[28] Melnikov, K-triviality in computable metric spaces, Proc. Amer. Math. Soc. 141 (8) pp 2885– (2013) · Zbl 1271.03059 · doi:10.1090/S0002-9939-2013-11528-5
[29] Merkle, The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, J. Symb. Log. 68 (4) pp 1362– (2003) · Zbl 1065.03024 · doi:10.2178/jsl/1067620192
[30] Merkle, Some results on effective randomness, Theor. Comput. Syst. 39 (5) pp 707– (2006) · Zbl 1100.03034 · doi:10.1007/s00224-005-1212-8
[31] Merkle, Kolmogorov-Loveland randomness and stochasticity, Ann. Pure Appl. Log. 138 (1-3) pp 183– (2006) · Zbl 1097.03041 · doi:10.1016/j.apal.2005.06.011
[32] Miller, Degrees of unsolvability of continuous functions, J. Symb. Log. 69 (2) pp 555– (2004) · Zbl 1070.03026 · doi:10.2178/jsl/1082418543
[33] Miyabe, Truth-table Schnorr randomness and truth-table reducible randomness, Math. Log. Q. 57 (3) pp 323– (2011) · Zbl 1220.03043 · doi:10.1002/malq.200910128
[34] Miyabe, L1-computability, layerwise computability and Solovay reducibility, Comput. 2 (1) pp 15– (2013)
[35] Miyabe, Algorithmic randomness over general spaces, Math. Log. Q. 60 (3) pp 184– (2014) · Zbl 1338.03084 · doi:10.1002/malq.201200051
[36] Muchnik, Mathematical metaphysics of randomness, Theor. Comput. Sci. 207 (2) pp 263– (1998) · Zbl 0922.60014 · doi:10.1016/S0304-3975(98)00069-3
[37] Nies, Computability and Randomness, Oxford Logic Guides Vol. 51 (2009) · Zbl 1237.03027 · doi:10.1093/acprof:oso/9780199230761.001.0001
[38] Pathak, Schnorr randomness and the Lebesgue differentiation theorem, Proc. Amer. Math. Soc. 142 (1) pp 335– (2014) · Zbl 1307.03027 · doi:10.1090/S0002-9939-2013-11710-7
[39] Pour-El, Perspectives in Mathematical Logic (1989)
[40] Schnorr, A unified approach to the definition of random sequences, Math. Syst. Theor. 5 pp 246– (1971) · Zbl 0227.62005 · doi:10.1007/BF01694181
[41] Schnorr, General random sequences and learnable sequences, J. Symb. Log. 42 (3) pp 329– (1977) · Zbl 0376.02026 · doi:10.2307/2272862
[42] Schröder, Admissible representations for probability measures, Math. Log. Q. 53 (4-5) pp 431– (2007) · Zbl 1124.03019 · doi:10.1002/malq.200710010
[43] J. G. Silveira Invariancia por cambio de base de la aleatoriedad computable y la aleatoriedad con recursos acotados Master’s thesis University of Buenos Aires 2011
[44] Turetsky, Logic Blog 2014 (2015)
[45] V’yugin, Ergodic theorems for individual random sequences, Theor. Comput. Sci. 207 (2) pp 343– (1998) · Zbl 0915.68092 · doi:10.1016/S0304-3975(98)00072-3
[46] Weihrauch, Texts in Theoretical Computer Science. An EATCS Series (2000)
[47] Williams, Probability with Martingales, Cambridge Mathematical Textbooks (1991) · Zbl 0722.60001 · doi:10.1017/CBO9780511813658
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.