Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Mutual Dimension and Random Sequences
verfasst von : Adam Case, Jack H. Lutz
Erschienen in: Mathematical Foundations of Computer Science 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.