Mutual dimension and random sequences.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 129565926 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Mutual dimension and random sequences. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Case%2C+Adam%22">Case, Adam</searchLink><relatesTo>1</relatesTo><i> adam.case@drake.edu</i><br /><searchLink fieldCode="AR" term="%22Lutz%2C+Jack+H%2E%22">Lutz, Jack H.</searchLink><relatesTo>2</relatesTo><i> lutz@iastate.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Jun2018, Vol. 731, p68-87. 20p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Dimension+theory+%28Topology%29%22">Dimension theory (Topology)</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+sequences%22">Mathematical sequences</searchLink><br /><searchLink fieldCode="DE" term="%22Probability+theory%22">Probability theory</searchLink><br /><searchLink fieldCode="DE" term="%22Kolmogorov+complexity%22">Kolmogorov complexity</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=129565926 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.tcs.2018.04.003 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 20 StartPage: 68 Subjects: – SubjectFull: Dimension theory (Topology) Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Mathematical sequences Type: general – SubjectFull: Probability theory Type: general – SubjectFull: Kolmogorov complexity Type: general Titles: – TitleFull: Mutual dimension and random sequences. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Case, Adam – PersonEntity: Name: NameFull: Lutz, Jack H. IsPartOfRelationships: – BibEntity: Dates: – D: 30 M: 06 Text: Jun2018 Type: published Y: 2018 Identifiers: – Type: issn-print Value: 03043975 Numbering: – Type: volume Value: 731 Titles: – TitleFull: Theoretical Computer Science Type: main |
| ResultId | 1 |
