Advertisement
Published in:
2015 | OriginalPaper | Chapter
Mutual Dimension and Random Sequences
Authors : Adam Case, Jack H. Lutz
Published in: Mathematical Foundations of Computer Science 2015
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
If S and T are infinite sequences over a finite alphabet, then the lower and upper mutual dimensions mdim(S : T) and Mdim(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 \(mdim(R_1:R_2)\) and \(Mdim(R_1:R_2)\), and we show that the condition \(Mdim(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 mdim(S : T) and Mdim(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 dim(S), Dim(S), dim(T), and Dim(T) that were developed and applied by Lutz and Mayordomo; and we prove a divergence formula for the values of these generalized mutual dimensions.