Bibliographic Details
| Title: |
Mutual dimension and random sequences. |
| Authors: |
Case, Adam1 adam.case@drake.edu, Lutz, Jack H.2 lutz@iastate.edu |
| Source: |
Theoretical Computer Science. Jun2018, Vol. 731, p68-87. 20p. |
| Subjects: |
Dimension theory (Topology), Algorithms, Mathematical sequences, Probability theory, Kolmogorov complexity |
| Abstract: |
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. [ABSTRACT FROM AUTHOR] |
|
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
