We compare various notions of algorithmic randomness. First we
consider relativized randomness. A set is n-random if it is
Martin-Löf random relative to ∅(n-1). We show that a
set is 2-random if and only if there is a constant c such that
infinitely many initial segments x of the set are
c-incompressible: C(x) ≥ |x|-c. The ‘only if' direction was
obtained independently by Joseph Miller. This characterization can be
extended to the case of time-bounded C-complexity.
Next we prove some results on lowness. Among other things, we
characterize the 2-random sets as those 1-random sets that are low for
Chaitin's Ω. Also, 2-random sets form minimal pairs with
2-generic sets. The r.e. low for Ω sets coincide with the
r.e. K-trivial ones.
Finally we show that the notions of Martin-Löf randomness, recursive
randomness, and Schnorr randomness can be separated in every high
degree while the same notions coincide in every non-high degree. We
make some remarks about hyperimmune-free and PA-complete degrees.