Mutual dimension and random sequences

If S and T are infinite sequences over a finite alphabet, then the lower and upper mutual dimensions m d i m ( S: T ) and M d i m ( S: T ) are the upper and lower densities of the algorithmic information that is shared by S and T. In this paper we investigate the relationships between mutual dimension and coupled randomness, which is the algorithmic randomness of two sequences R 1 and R 2 with respect to probability measures that may be dependent on one another. For a restricted but interesting class of coupled probability measures we prove an explicit formula for the mutual dimensions m d i m ( R 1: R 2 ) and M d i m ( R 1: R 2 ), and we show that the condition M d i m ( R 1: R 2 ) = 0 is necessary but not sufficient for R 1 and R 2 to be independently random. We also identify conditions under which Billingsley generalizations of the mutual dimensions m d i m ( S: T ) and M d i m ( S: T ) can be meaningfully defined; we show that under these conditions these generalized mutual dimensions have the “correct” relationships with the Billingsley generalizations of d i m ( S ), D i m ( S ), d i m ( T ), and D i m ( T ) that were developed and applied by Lutz and Mayordomo; and we prove a divergence formula for the values of these generalized mutual dimensions.

Authors

• Adam Case
• Jack H. Lutz

Keywords

• Algorithmic information theory
• Coupled randomness
• Effective fractal dimensions
• Kolmogorov complexity
• Mutual information