Relative Randomness
As each of the equivalent definitions of a Martin-Löf random sequence is based on what is computable by some Turing machine, one can naturally ask what is computable by a Turing oracle machine. For a fixed oracle A, a sequence B which is not only random but in fact satisfies the equivalent definitions for computability relative to A (e.g., no martingale which is constructive relative to the oracle A succeeds on B) is said to be random relative to A. Two sequences, while themselves random, may contain very similar information, and therefore neither will be random relative to the other. Any time there is a Turing reduction from one sequence to another, the second sequence cannot be random relative to the first, just as computable sequences are themselves nonrandom; in particular, this means that Chaitin's Ω is not random relative to the halting problem.
An important result relating to relative randomness is van Lambalgen's theorem, which states that if C is the sequence composed from A and B by interleaving the first bit of A, the first bit of B, the second bit of A, the second bit of B, and so on, then C is algorithmically random if and only if A is algorithmically random, and B is algorithmically random relative to A. A closely related consequence is that if A and B are both random themselves, then A is random relative to B if and only if B is random relative to A.
Read more about this topic: Algorithmically Random Sequence
Famous quotes containing the word relative:
“Personal change, growth, development, identity formation—these tasks that once were thought to belong to childhood and adolescence alone now are recognized as part of adult life as well. Gone is the belief that adulthood is, or ought to be, a time of internal peace and comfort, that growing pains belong only to the young; gone the belief that these are marker events—a job, a mate, a child—through which we will pass into a life of relative ease.”
—Lillian Breslow Rubin (20th century)