On partial randomness

If x = x(1)x(2) center dot center dot center dot x(n)center dot center dot center dot is a randorn sequence, then the sequence y = 0x(1)0x(2) center dot center dot center dot 0x(n)center dot center dot center dot is clearly not random; however, y seenis to be "about half' random", L. Staiger [Kolmogorov complexity and Hausdorff dimension, Inform. and Comput. 103 (1993) 159-194 and A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst. 31 (1998) 215-229] and K. Tadaki [A generalisation of Chaitin's halting probability Q and halting self-similar sets, Hokkaido Math. J. 31 (2002) 219-253] have studied the degree of randomness of sequences or reals by measuring their "degree of compression". This line of study leads to various definitions of partial randomness. In this paper we explore some relations between these definitions. Among other results we obtain a characterisation of Sigma(1)-dimension (as defined by Schnorr and Lutz in terms of martingales) in terms of strong Martin-Lof epsilon-tests (a variant of Martin-Lof tests), and we show that epsilon-randomness for epsilon epsilon (0, 1) is different (and more difficult to study) than the classical 1-randomness. (c) 2005 Elsevier B.V. All rights reserved.