zbMATH — the first resource for mathematics

Energy randomness. (English) Zbl 06976569
Summary: Energy randomness is a notion of partial randomness introduced by Kjos-Hanssen to characterize the sequences that can be elements of a Martin-Löf random closed set (in the sense of Barmpalias, Brodhead, Cenzer, Dashti and Weber). It brings together ideas from potential theory and algorithmic randomness. In this paper, we show that \(X \in 2^\omega\) is \(s\)-energy random if and only if \(\sum_{n \in \omega} 2^{sn - KM(X \upharpoonright n)} < \infty\), providing a characterization of energy randomness via a priori complexity \(KM\). This is related to a question of Allen, Bienvenu, and Slaman.

03D32 Algorithmic randomness and dimension
31C15 Potentials and capacities on other spaces
Full Text: DOI arXiv
[1] Allen, K.; Bienvenu, L.; Slaman, T. A., On zeros of martin-Löf random Brownian motion, Journal of Logic and Analysis, 6, 1-34, (2014) · Zbl 1346.03044
[2] Asarin, E. A.; Pokrovskiĭ, A. V., Application of Kolmogorov complexity to the analysis of the dynamics of controllable systems, Avtomatika i Telemekhanika, 1, 25-33, (1986)
[3] Barmpalias, G.; Brodhead, P.; Cenzer, D.; Dashti, S.; Weber, R., Algorithmic randomness of closed sets, Journal of Logic and Computation, 17, 1041-1062, (2007) · Zbl 1155.03031
[4] Day, A. R.; Miller, J. S., Randomness for non-computable measures, Transactions of the American Mathematical Society, 365, 3575-3591, (2013) · Zbl 1307.03026
[5] Diamondstone, D.; Kjos-Hanssen, B., Martin-Löf randomness and Galton-Watson processes, Annals of Pure and Applied Logic, 163, 519-529, (2012) · Zbl 1247.03085
[6] Fouché, W. L., The descriptive complexity of Brownian motion, Advances in Mathematics, 155, 317-343, (2000) · Zbl 0971.68077
[7] Gács, P., Exact expressions for some randomness tests, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 26, 385-394, (1980) · Zbl 0464.60004
[8] Higuchi, K.; Hudelson, W. M. P.; Simpson, S. G.; Yokoyama, K., Propagation of partial randomness, Annals of Pure and Applied Logic, 165, 742-758, (2014) · Zbl 1329.03078
[9] Kjos-Hanssen, B., Infinite subsets of random sets of integers, Mathematical Research Letters, 16, 103-110, (2009) · Zbl 1179.03061
[10] R. Lyons and Y. Peres, Probability on Trees and Networks, Cambridge Series in Statistical and Probabilistic Mathematics, Vol. 42, Cambridge University Press, New York, 2016. · Zbl 1376.05002
[11] Miller, J. S.; Yu, L., On initial segment complexity and degrees of randomness, Transactions of the American Mathematical Society, 360, 3193-3210, (2008) · Zbl 1140.68028
[12] Pemantle, R.; Peres, Y., Galton-Watson trees with the same mean have the same polar sets, Annals of Probability, 23, 1102-1124, (1995) · Zbl 0833.60085
[13] Reimann, J., Effectively closed sets of measures and randomness, Annals of Pure and Applied Logic, 156, 170-182, (2008) · Zbl 1153.03021
[14] Reimann, J.; Slaman, T. A., Measures and their random reals, Transactions of the American Mathematical Society, 367, 5081-5097, (2015) · Zbl 1375.03050
[15] Reimann, J.; Stephan, F., Hierarchies of randomness tests, 215-232, (2006), Hackensack, NJ · Zbl 1116.03038
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.