- Independence, Relative Randomness, and PA Degrees [pdf]
(with Adam Day)
To appear in Notre Dame Journal of Formal Logic
Abstract: We study pairs of reals that are mutually Martin-L\"{o}f random with respect to a common, not necessarily computable probability measure. We show that a generalized version of van Lambalgen's Theorem holds for non-computable probability measures, too. We study, for a given real A, the \emph{independence spectrum} of A, the set of all B so that there exists a probability measure \mu so that \mu\{A,B\} = 0 and (A,B) is \mu x \mu-random. We prove that if A is c.e., then no \Delta^0_2 set is in the independence spectrum of A. We obtain applications of this fact to PA degrees. In particular, we show that if A is c.e.\ and P is of PA degree so that P \not\ge_{\T} A, then A \oplus P \geqT \emptyset'.
- Randomness for continuous measures [pdf]
(with Theodore A. Slaman)
Revised Draft
Abstract: We study randomness with respect to arbitrary (that is, not necessarily computable) continuous measures. We show that for every n, the set NCR_n of reals that are not random with respect to a continuous probability measure is countable. The proof uses Borel determinacy and Kumabe-Slaman forcing. Furthermore, we show that for every k, the statement "For all n, NCR_n is countable." cannot be proven in ZFC(-) + "There exists k iterates of the power set of ω", where ZFC(-) denotes Zermelo-Fraenkel set theory with choice minus the power set axiom. The proof exhibits a model L_β such that NCR_n is cofinal in the Turing degrees of L_β. (L_β is a level of Goedel's constructible hierarchy.)
- Measures and their random reals [pdf]
(with Theodore A. Slaman)
To appear in Transactions of the AMS
Abstract: We study the randomness properties of reals with respect to arbitrary probability measures on Cantor space. We show that every non-recursive real is non-trivially random with respect to some measure. The probability measures constructed in the proof may have atoms. If one rules out the existence of atoms, i.e. considers only continuous measures, it turns out that every non-hyperarithmetical real is random for a continuous measure. On the other hand, examples of reals not random for a continuous measure can be found throughout the hyperarithmetical hierarchy.
- Probability measures and effective randomness [pdf]
(with Theodore A. Slaman)
To appear in: 13th International Congress of Logic Methodology and Philosophy of Science, Beijing, 2007
Abstract: This is a survey of recent work by the authors on randomness for continuous measures.
- Effectively closed classes of measures and randomness [pdf]
Annals of Pure and Applied Logic, 156(1), pp 170--182, 2008.
Abstract: We show that if a real $x \in \Cant$ is strongly Hausdorff $\Hm{h}$-random, where $h$ is a dimension function corresponding to a convex order, then it is also random for a continuous probability measure $\mu$ such that the $\mu$-measure of the basic open cylinders shrinks according to $h$. The proof uses a new method to construct measures, based on effective (partial) continuous transformations and a basis theorem for $\Pi^0_1$-classes applied to closed sets of probability measures. We use the main result to give a new proof of Frostman's Lemma, to derive a collapse of randomness notions for Hausdorff measures, and to provide a characterization of effective Hausdorff dimension similar to Frostman's Theorem.
- Randomness beyond Lebesgue measure [pdf]
Logic Colloquium 06, Nijmegen. To appear.
Abstract: Much of the recent research on algorithmic randomness has focused on randomness for Lebesgue measure.
While, from a computability theoretic point of view, the picture remains unchanged if one passes to arbitrary computable measures, interesting phenomena occur if one studies the the set of reals which are random for an arbitrary measure on Cantor space.
This paper tries to give a survey of the research that has been done on randomness for non-Lebesgue measures.
- A lower cone in the wtt degrees of non-integral effective dimension [pdf]
(with Andre Nies)
Proceedings of IMS workshop on Computational Prospects of Infinity, Part II, National University of Singapore, World Scientific, 2008.
Abstract: For any rational number r, we show that there exists a set A (weak truth-table reducible to the halting problem) such that any set B weak truth-table reducible to it has effective Hausdorff dimension at most r, where A itself has dimension at least r. This implies, for any rational r, the existence of a wtt-lower cone of effective dimension r.
- Schnorr dimension [pdf]
(with Rodney G. Downey and Wolfgang Merkle)
Mathematical Structures in Computer Science, 16(5), pp 789-811, 2006.
(an earlier version appeared in: Computability in Europe, LNCS 3526, pp. 96--105, Springer, 2005)
Abstract: Following Lutz's approach to effective (constructive) dimension, we define a
notion of dimension for individual sequences based on Schnorr's concept(s) of
randomness. In contrast to computable randomness and Schnorr randomness, the
dimension concepts defined via computable martingales and Schnorr tests
coincide, i.e.\ the Schnorr Hausdorff dimension of a sequence always equals its
computable Hausdorff dimension. Furthermore, we give a machine characterization
of Schnorr dimension, based on prefix-free machines whose domain has computable
measure. Finally, we show that there exist computably enumerable sets which are
Schnorr (computably) irregular: while every c.e. set has Schnorr Hausdorff
dimension 0 there are c.e. sets of computable packing dimension 1, a
property impossible in the case of effective (constructive) dimension, due to
Barzdins' Theorem. In fact, we prove that every hyperimmune Turing degree
contains a set of computable packing dimension 1.
- On hierarchies of randomness tests [pdf]
(with Frank Stephan)
Mathematical Logic in Asia, Proceedings of the 9th Asian Logic Conference, Novosibirsk, World Scientific Publishing, 2006
Abstract: It is well known that Martin-Löf randomness can be characterized by a number
of equivalent test concepts, based either on effective nullsets (Martin-Löf
and Solovay tests) or on prefix-free Kolmogorov complexity (lower and upper
entropy). These equivalences are not preserved as regards the partial
randomness notions induced by effective Hausdorff measures or partial
incompressibility. Tadaki [2002]
and Calude, Staiger and Terwijn [2005]
studied several concepts of partial randomness, but for some of them the exact
relations remained unclear. In this paper we will show that they form a proper
hierarchy of randomness notions, namely for any r of the form
r(x) = 2^(-|x|s) with s being a rational number strictly between 0 and 1,
the Martin-Löf r-tests are strictly weaker than Solovay r-tests
which in turn are strictly weaker than strong Martin-L\"of r-tests.
These results also hold for a more general class of r introduced as unbounded premeasures.
- On selection functions that do not preserve normality [pdf]
(with Wolfgang Merkle)
Theory of Computing Systems 39(5):685-697, 2006.
(an earlier version appeared in: Mathematical foundations of computer science 2003, LNCS 2747, pp. 602--611, Springer, 2003)
Abstract: The sequence selected from a sequence R(0)R(1)... by a
language L is the subsequence of R that contains exactly the
bits R(n+1) such that the prefix R(0)...R(n) is in L. By a
result of Agafonoff, a
sequence is normal if and only if any subsequence selected by a
regular language is again normal. Kamae and Weiss and others have raised the
question of how complex a language must be such that selecting
according to the language does not preserve normality. We show that
there are such languages that are only slightly more complicated than
regular ones, namely, normality is preserved neither by deterministic
one-counter languages nor by linear languages.
In fact, for both types of languages it is possible to select a
constant sequence from a normal one.
- Kolmogorov-Loveland randomness and stochasticity [pdf]
(with Woflgang Merkle, Joseph Miller, André Nies, and Frank Stephan)
Annals of Pure and Applied Logic, 138(1-3):183--210, 2005.
(an earlier version appeared in: STACS 2005 (Stuttgart), LNCS 3404, pp. 422--433, Springer, 2005)
Abstract: An infinite binary sequence X is Kolmogorov-Loveland (or KL) random if there
is no
computable non-monotonic betting strategy that succeeds on X.
A sequence X is KL-stochastic if there is no computable non-monotonic
selection rule that selects from X an infinite, biased sequence.
One of the major open problems in the field of effective randomness is whether
Martin-Löf randomness is the same as KL-randomness. Our first main result
states that KL-random sequences are close to Martin-Löf random sequences in
so far as every KL-random sequence has arbitrarily dense subsequences that are
Martin-Löf random. However, this does not characterize
KL-randomness; we construct a sequence that is not even computably random such
that every effective split yields two subsequences that are 2-random.
Furthermore, we show for any KL-random sequence A that is computable in the
halting problem that, first, for any effective split of A both halves are
Martin-Löf random and, second, for any computable, nondecreasing, and
unbounded function g and almost all n, the prefix of A of length n has
prefix-free Kolmogorov complexity at least n-g(n). Again, the latter
property does not characterize KL-randomness; we construct a left-r.e.\ sequence that has this property but is not
KL-stochastic, in fact, is not even Mises-Wald-Church stochastic.
Furthermore, we construct a non-empty effectively closed class of KL-stochastic sequences that are
not weakly 1-random. Another result asserts that every KL-stochastic sequence has
effective dimension 1. This improves
on a result by Muchnik.
- Effective Hausdorff dimension [pdf]
(with Frank Stephan)
Baaz, Friedman, Krajicek (eds.), Logic Colloquium '01, Association for Symbolic Logic, 2005.
Abstract: We continue the study of effective Hausdorff dimension
as it was initiated by Lutz. Whereas he uses a
generalization of martingales on the Cantor space to
introduce this notion we give a characterization in
terms of effective s-dimensional Hausdorff measures,
similar to the effectivization of Lebesgue measure by
Martin-Löf. It turns out that effective
Hausdorff dimension allows to classify sequences
according to their `degree' of algorithmic randomness,
i.e., their algorithmic density of information.
Earlier the works of Staiger and Ryabko
showed a deep connection between Kolmogorov complexity
and Hausdorff dimension. We further develop this
relationship and use it to give effective versions of
some important properties of (classical) Hausdorff
dimension. Finally, we determine the effective
dimension of some objects arising in the context of
computability theory, such as degrees and spans.
- Computability and Fractal Dimension[pdf]
Doctoral Dissertation, Universität Heidelberg, 2004.
- Almost complete sets [pdf]
(with Klaus Ambos-Spies, Wolfgang Merkle and Sebastiaan A. Terwijn)
Theoretical Compter Science 306:177-194, 2003.
(an earlier version appeared in: STACS 2000 (Lille), LNCS 1770, pp. 419--430, Springer, 2000)
Abstract: We show that there is a set which is almost complete but not complete
under polynomial-time many-one reductions for the class
E.
Here a set A in a complexity class C is almost
complete for C under some reducibility r if the
class of the problems in
C which do not r-reduce to A has measure 0
in C in the sense of Lutz's resource-bounded
measure theory. We also show that the almost complete sets
for E under polynomial-time bounded one-one length-increasing
reductions
and truth-table reductions of norm 1 coincide with the
almost p-m-complete sets for E.
Moreover, we obtain similar results for the class EXP.
- Hausdorff dimension in exponential time [pdf]
(with Klaus Ambos-Spies, Wolfgang Merkle, and Frank Stephan)
Proc. 16th Conference on Computational Complexity, pp. 210--217, IEEE Computer Society, 2001.
Abstract:In this paper we investigate effective versions of Hausdorff dimension
which have been recently introduced by Lutz.
We focus on dimension in the class E of sets computable in
linear exponential time.
We determine the dimension of various classes related to fundamental structural properties
including different types of autoreducibility and immunity. By a
new general invariance theorem for resource-bounded dimension we show that the
class of p-m-complete sets for E has dimension 1 in E. Moreover,
we show that there are p-m-lower spans in E of dimension
H(s) for any rational s between 0 and 1,
where H(s) is the
binary entropy function. This leads to a new general completeness notion for
E that properly extends Lutz's concept of weak completeness. Finally we
characterize resource-bounded dimension in terms of martingales with restricted betting ratios and in terms of prediction functions.
- Effective Baire category concepts [pdf]
(with Klaus Ambos-Spies)
Proc. Sixth Asian Logic Conference 1996, pp. 13--29, Singapore University Press, 1998.
Abstract: Mehlhorn [1973] introduced an effective Baire category concept designed for measuring the size of computable sets. This concept is based on effective extension functions. By considering partial extension functions, we introduce a stronger concept. Similar resource-bounded concepts have been previously introduced by Ambos-Spies et al. [1988] and Ambos-Spies [1996]. By defining a new variant of the Banach-Mazur game, we give a game theoretical characterization of our category concept.
- Topologische Spiele und resourcenbeschränkte Baire-Kategorie [pdf]
Diploma Thesis, Universität Heidelberg, 1997.