×

zbMATH — the first resource for mathematics

Schnorr randomness for noncomputable measures. (English) Zbl 06820656
Summary: This paper explores a novel definition of Schnorr randomness for noncomputable measures. We say \(x\) is uniformly Schnorr \(\mu\)-random if \(t(\mu,x)<\infty\) for all lower semicomputable functions \(t(\mu,x)\) such that \(\mu \mapsto \int t(\mu,x)d\mu(x)\) is computable. We prove a number of theorems demonstrating that this is the correct definition which enjoys many of the same properties as Martin-Löf randomness for noncomputable measures. Nonetheless, a number of our proofs significantly differ from the Martin-Löf case, requiring new ideas from computable analysis.
MSC:
03D32 Algorithmic randomness and dimension
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Martin-Löf, P., The definition of random sequences, Inf. Control, 9, 602-619, (1966) · Zbl 0244.62008
[2] Schnorr, C.-P., Eine bemerkung zum begriff der zufälligen folge, Z. Wahrscheinlichkeitstheor. Verw. Geb., 14, 27-35, (1969/1970), (in German, English summary) · Zbl 0188.02805
[3] Brattka, V.; Miller, J. S.; Nies, A., Randomness and differentiability, Trans. Am. Math. Soc., 368, 1, 581-605, (2016) · Zbl 1402.03062
[4] Rute, J., Topics in algorithmic randomness and computable analysis, (2013), Carnegie Mellon University, available at · Zbl 1364.03062
[5] Pathak, N.; Rojas, C.; Simpson, S. G., Schnorr randomness and the Lebesgue differentiation theorem, Proc. Am. Math. Soc., 142, 1, 335-349, (2014) · Zbl 1307.03027
[6] Levin, L. A., Uniform tests for randomness, Dokl. Akad. Nauk SSSR, Sov. Math. Dokl., 17, 2, 337-340, (1976), (in Russian), English translation: · Zbl 0341.94013
[7] Gács, P., Uniform test of algorithmic randomness over a general space, Theor. Comput. Sci., 341, 1-3, 91-137, (2005) · Zbl 1077.68038
[8] Reimann, J., Effectively closed sets of measures and randomness, Ann. Pure Appl. Logic, 156, 1, 170-182, (2008) · Zbl 1153.03021
[9] Reimann, J.; Slaman, T. A., Measures and their random reals, Trans. Am. Math. Soc., 367, 7, 5081-5097, (2015) · Zbl 1375.03050
[10] Day, A. R.; Miller, J. S., Randomness for non-computable measures, Trans. Am. Math. Soc., 365, 7, 3575-3591, (2013) · Zbl 1307.03026
[11] Kjos-Hanssen, B., The probability distribution as a computational resource for randomness testing, J. Log. Anal., 2, 10, 1-13, (2010) · Zbl 1286.68251
[12] Bienvenu, L.; Gács, P.; Hoyrup, M.; Rojas, C.; Shen, A., Algorithmic tests and randomness with respect to a class of measures, Proc. Steklov Inst. Math., 274, 1, 34-89, (2011) · Zbl 1294.03032
[13] Bienvenu, L.; Monin, B., Von Neumann’s biased coin revisited, (Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, (2012), IEEE Computer Soc. Los Alamitos, CA), 145-154 · Zbl 1364.03059
[14] Day, A. R.; Reimann, J., Independence, relative randomness, and PA degrees, Notre Dame J. Form. Log., 55, 1, 1-10, (2014) · Zbl 1332.03010
[15] Hoyrup, M., Randomness and the ergodic decomposition, (Models of Computation in Context, Lecture Notes in Comput. Sci., vol. 6735, (2011), Springer Heidelberg), 122-131 · Zbl 1259.03057
[16] Kjos-Hanssen, B., Infinite subsets of random sets of integers, Math. Res. Lett., 16, 1, 103-110, (2009) · Zbl 1179.03061
[17] Diamondstone, D.; Kjos-Hanssen, B., Martin-Löf randomness and Galton-Watson processes, Ann. Pure Appl. Logic, 163, 5, 519-529, (2012) · Zbl 1247.03085
[18] Schnorr, C.-P., Zufälligkeit und wahrscheinlichkeit. eine algorithmische begründung der wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, vol. 218, (1971), Springer-Verlag Berlin, (in German) · Zbl 0232.60001
[19] Downey, R. G.; Hirschfeldt, D. R., Algorithmic randomness and complexity, Theory and Applications of Computability, (2010), Springer New York · Zbl 1221.68005
[20] Miyabe, K.; Van Rute, J., Lambalgen’s theorem for uniformly relative Schnorr and computable randomness, (Proceedings of the 12th Asian Logic Conference, (2013), World Sci. Publ. Hackensack, NJ), 251-270 · Zbl 1364.03062
[21] Yu, L., When Van Lambalgen’s theorem fails, Proc. Am. Math. Soc., 135, 3, 861-864, (2007) · Zbl 1110.03027
[22] van Lambalgen, M., The axiomatization of randomness, J. Symb. Log., 55, 3, 1143-1167, (1990) · Zbl 0724.03026
[23] Franklin, J. N.Y.; Stephan, F., Schnorr trivial sets and truth-table reducibility, J. Symb. Log., 75, 2, 501-521, (2010) · Zbl 1193.03073
[24] Allen, K.; Bienvenu, L.; Slaman, T. A., On zeros of martin-Löf random Brownian motion, J. Log. Anal., 6, 9, 1-34, (2014) · Zbl 1346.03044
[25] Miller, J. S.; Rute, J., Energy randomness, Isr. J. Math., (2017), in press
[26] Soare, R. I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, (1987), Springer-Verlag Berlin · Zbl 0623.03042
[27] Brattka, V.; Hertling, P.; Weihrauch, K., A tutorial on computable analysis, (New Computational Paradigms, (2008), Springer New York), 425-491 · Zbl 1145.03037
[28] Tao, T., An introduction to measure theory, Graduate Studies in Mathematics, vol. 126, (2011), American Mathematical Society Providence, RI · Zbl 1231.28001
[29] Billingsley, P., Probability and measure, Wiley Series in Probability and Mathematical Statistics, (1995), John Wiley & Sons, Inc. New York, a Wiley-Interscience Publication · Zbl 0822.60002
[30] Kallenberg, O., Random measures, (1983), Akademie-Verlag, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers] Berlin, London · Zbl 0288.60053
[31] Hoyrup, M.; Rojas, C., Computability of probability measures and martin-Löf randomness over metric spaces, Inf. Comput., 207, 7, 830-847, (2009) · Zbl 1167.68023
[32] Miyabe, K., \(L^1\)-computability, layerwise computability and Solovay reducibility, Computability, 2, 1, 15-29, (2013) · Zbl 1315.03073
[33] Nies, A., Computability and randomness, Oxford Logic Guides, vol. 51, (2009), Oxford University Press Oxford · Zbl 1169.03034
[34] Li, M.; Vitányi, P., An introduction to Kolmogorov complexity and its applications, Texts in Computer Science, (2008), Springer New York · Zbl 1185.68369
[35] Gács, P., Lecture notes on descriptional complexity and randomness, available at
[36] Weihrauch, K., On computable metric spaces tietze-Urysohn extension is computable, (Computability and Complexity in Analysis, Swansea, 2000, Lecture Notes in Comput. Sci., vol. 2064, (2001), Springer Berlin), 357-368 · Zbl 0985.03033
[37] Simpson, S. G.; Stephan, F., Cone avoidance and randomness preservation, Ann. Pure Appl. Logic, 166, 6, 713-728, (2015) · Zbl 1371.03052
[38] Miyabe, K., Truth-table Schnorr randomness and truth-table reducible randomness, Math. Log. Q., 57, 3, 323-338, (2011) · Zbl 1220.03043
[39] Bauwens, B., Van Lambalgen’s theorem fails for some computable measure, submitted for publication, available at
[40] Bauwens, B.; Shen, A.; Takahashi, H., Conditional probabilities and Van Lambalgen’s theorem revisited, Theory Comput. Syst., 61, 4, 1315-1336, (2017), published online 2017 · Zbl 1420.03099
[41] Ackerman, N. L.; Freer, C. E.; Roy, D. M., Noncomputable conditional distributions, (26th Annual IEEE Symposium on Logic in Computer Science, LICS 2011, (2011), IEEE Computer Soc. Los Alamitos, CA), 107-116
[42] Takahashi, H., On a definition of random sequences with respect to conditional probability, Inf. Comput., 206, 12, 1375-1382, (2008) · Zbl 1208.03046
[43] Takahashi, H., Algorithmic randomness and monotone complexity on product space, Inf. Comput., 209, 2, 183-197, (2011) · Zbl 1215.68115
[44] Hoyrup, M.; Rojas, C., Applications of effective probability theory to martin-Löf randomness, (Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci., vol. 5555, (2009), Springer Berlin), 549-561 · Zbl 1248.03066
[45] Bienvenu, L.; Porter, C., Strong reductions in effective randomness, Theor. Comput. Sci., 459, 55-68, (2012) · Zbl 1283.68170
[46] Rute, J., When does randomness come from randomness?, Theor. Comput. Sci., 635, 35-50, (2016) · Zbl 1339.68127
[47] Pitman, J., Brownian motion, bridge, excursion, and meander characterized by sampling at independent uniform times, Electron. J. Probab., 4, 11, 1-33, (1999) · Zbl 0935.60068
[48] Bienvenu, L.; Hoyrup, M.; Shen, A., Layerwise computability and image randomness, Theory Comput. Syst., 61, 4, 1353-1375, (2017), published online 2017 · Zbl 1395.68159
[49] Kjos-Hanssen, B.; Nies, A.; Stephan, F., Lowness for the class of Schnorr random reals, SIAM J. Comput., 35, 3, 647-657, (2005) · Zbl 1095.68043
[50] Franklin, J. N.Y., Lowness and highness properties for randomness notions, (10th Asian Logic Conference, (2010), World Sci. Publ. Hackensack, NJ), 124-151 · Zbl 1193.03072
[51] Bienvenu, L.; Miller, J. S., Randomness and lowness notions via open covers, Ann. Pure Appl. Logic, 163, 5, 506-518, (2012) · Zbl 1250.03067
[52] Merkle, W.; Miller, J. S.; Nies, A.; Reimann, J.; Stephan, F., Kolmogorov-loveland randomness and stochasticity, Ann. Pure Appl. Logic, 138, 1-3, 183-210, (2006) · Zbl 1097.03041
[53] Schnorr, C.-P.; Fuchs, P., General random sequences and learnable sequences, J. Symb. Log., 42, 3, 329-340, (1977) · Zbl 0376.02026
[54] Schnorr, C.-P., A survey of the theory of random sequences, (Basic Problems in Methodology and Linguistics, Proc. Fifth Internat. Congr. Logic, Methodology and Philos. of Sci., Part III, Univ. Western Ontario, London, Ont., 1975, Univ. Western Ontario Ser. Philos. Sci., vol. 11, (1977), Reidel Dordrecht), 193-211
[55] Bauwens, B., Uniform Van Lambalgen’s theorem fails for computable randomness, available at
[56] Hoyrup, M.; Rojas, C., An application of martin-Löf randomness to effective probability theory, (Mathematical Theory and Computational Practice, Lecture Notes in Comput. Sci., vol. 5635, (2009), Springer Berlin), 260-269 · Zbl 1268.03055
[57] Hoyrup, M., Computability of the ergodic decomposition, Ann. Pure Appl. Logic, 164, 5, 542-549, (2013) · Zbl 1271.03063
[58] Barmpalias, G.; Greenberg, N.; Montalbán, A.; Slaman, T. A., K-trivials are never continuously random, (Proceedings of the 11th Asian Logic Conference, (2012), World Sci. Publ. Hackensack, NJ), 51-58 · Zbl 1296.03022
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.