zbMATH — the first resource for mathematics

Kolmogorov-Loveland stochasticity and Kolmogorov complexity. (English) Zbl 1204.68110
Summary: W. Merkle, J. S. Miller, A. Nies, J. Reimann and F. Stephan [Ann. Pure Appl. Logic 138, No. 1–3, 183–210 (2006; Zbl 1097.03041)] showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than \(\mathcal {H}(\frac {1}{2}+\delta)\) (\(\mathcal H\) being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least \(\delta \). We also prove an analogous result for finite strings.

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI
[1] Ambos-Spies, K., Mayordomo, E., Wang, Y., Zheng, X.: Resource-bounded balanced genericity, stochasticity and weak randomness. In: Symposium on Theoretical Aspects of Computer Science (STACS 1996). Lecture Notes in Computer Science, vol. 1046, pp. 63–74. Springer, Berlin (1996) · Zbl 1379.68185
[2] Asarin, E.: Some properties of Kolmogorov {\(\Delta\)}-random sequences. Theory Probab. Appl. 32, 507–508 (1987) · Zbl 0648.60006
[3] Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, in preparation · Zbl 1221.68005
[4] Downey, R., Merkle, W., Reimann, J.: Schnorr dimension. In: Springer (ed.) Conference on Computability in Europe (CiE 2005). Lecture Notes in Computer Science, vol. 3526, pp. 96–105. Springer, Berlin (2005) · Zbl 1113.03331
[5] Durand, B., Vereshchagin, N.: Kolmogorov-Loveland stochasticity for finite strings. Inf. Process. Lett. 91(6), 263–269 (2004) · Zbl 1177.60008
[6] Falconer, K.: The Geometry of Fractal Sets. Cambridge University Press, Cambridge (1985) · Zbl 0587.28004
[7] Hausdorff, F.: Dimension und äusseres mass. Math. Ann. 79, 157–179 (1919) · JFM 46.0292.01
[8] Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 2nd edn. Graduate Texts in Computer Science. Springer, Berlin (1997)
[9] Lutz, J.: Dimension in complexity classes. SIAM J. Comput. 32, 1236–1259 (2003) · Zbl 1026.68059
[10] Lutz, J.: The dimensions of individual strings and sequences. Inf. Comput. 187, 49–79 (2003) · Zbl 1090.68053
[11] Mayordomo, E.: A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett. 84, 1–3 (2002) · Zbl 1045.68570
[12] Merkle, W.: The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences. J. Symb. Log. 68, 1362–1376 (2003) · Zbl 1065.03024
[13] Merkle, W., Miller, J.S., Nies, A., Reimann, J., Stephan, F.: Kolmogorov-Loveland randomness and stochasticity. Ann. Pure Appl. Log. 138(1–3), 183–210 (2006) · Zbl 1097.03041
[14] Muchnik, A.A., Semenov, A., Uspensky, V.: Mathematical metaphysics of randomness. Theor. Comput. Sci. 207(2), 263–317 (1998) · Zbl 0922.60014
[15] Schnorr, C.: Zufälligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, vol. 218. Springer, Berlin-Heidelberg-New York (1971) · Zbl 0232.60001
[16] Shen, A.: On relations between different algorithmic definitions of randomness. Sov. Math. Dokl. 38, 316–319 (1989) · Zbl 0683.60002
[17] van Lambalgen, M.: Random sequences. Ph.D. thesis, University of Amsterdam, Amsterdam (1987) · Zbl 0628.60001
[18] Zvonkin, A., Levin, L.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Surv. 25(6), 83–124 (1970) · Zbl 0222.02027
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.