The van Lambalgen theorem is a surprising result in algorithmic information theory concerning the symmetry of relative randomness. It establishes that for any pair of infinite sequences A and B, B is Martin-Lof random and A is Martin-Lof random relative to B if and only if the interleaved sequence A(+)B is Martin-Lof random. This implies that A is relative random to B if and only if B is random relative to A [1-3]. This paper studies the validity of this phenomenon for different notions of time-bounded relative randomness. We prove the classical van Lambalgen theorem using martingales and Kolmogorov compressibility. We establish the failure of relative randomness in these settings, for both time-bounded martingales and time-bounded Kolmogorov complexity. We adapt our classical proofs when applicable to the time-bounded setting, and construct counterexamples when they fail. The mode of failure of the theorem may depend on the notion of time-bounded randomness.
展开▼
