Randomness and invariance.
Saved in:
| Title: | Randomness and invariance. |
|---|---|
| Authors: | Persiau, Floris1 (AUTHOR), Blando, Francesca Zaffora2 (AUTHOR) |
| Source: | Journal of Logic & Computation. Dec2025, Vol. 35 Issue 8, p1-31. 31p. |
| Subjects: | Algorithmic randomness, Probability measures, Mathematical symmetry, Binary sequences, Von Mises, Ludwig, 1881-1973, Mathematical equivalence, Stochastic processes |
| Abstract: | Richard von Mises was the first to provide a rigorous definition of randomness for infinite binary sequences, taken to represent indefinitely long sequences of experimental outcomes or indefinitely large (ordered) population samples. According to von Mises, a sequence is random if, within it, the relative frequencies of 0 and 1 each converge to a finite limit, and these limiting relative frequencies are invariant under a class of transformations that he called selection rules. While the notion of randomness defined by von Mises is known to have some serious limitations, his theory was pivotal to the development of algorithmic randomness: a branch of computability theory that provides the now-standard approach to defining randomness for individual mathematical objects. The purpose of this article is to call attention to the fact that, despite its flaws, one of the core ideas behind von Mises' account of randomness also underlies much of the theory of algorithmic randomness. In particular, we bring together and generalize a number of little-known results, proving that, for a broad class of probability measures, several canonical algorithmic randomness notions are characterizable in terms of invariance: i.e. in terms of the preservation, or the stable satisfaction, of various natural properties under a class of transformations that can be seen as a generalization of von Mises' selection rules. Many of the properties in question are usually described as 'minimal randomness properties': they are not in themselves sufficient for randomness, but they are often taken to be necessary (or at least desirable) for it. From this perspective, our results establish that algorithmic randomness coincides with the stable satisfaction of various minimal randomness properties (including the existence of limiting relative frequencies, as in von Mises' original account). [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA 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: 190650841 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Randomness and invariance. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Persiau%2C+Floris%22">Persiau, Floris</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Blando%2C+Francesca+Zaffora%22">Blando, Francesca Zaffora</searchLink><relatesTo>2</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Journal+of+Logic+%26+Computation%22">Journal of Logic & Computation</searchLink>. Dec2025, Vol. 35 Issue 8, p1-31. 31p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Algorithmic+randomness%22">Algorithmic randomness</searchLink><br /><searchLink fieldCode="DE" term="%22Probability+measures%22">Probability measures</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+symmetry%22">Mathematical symmetry</searchLink><br /><searchLink fieldCode="DE" term="%22Binary+sequences%22">Binary sequences</searchLink><br /><searchLink fieldCode="DE" term="%22Von+Mises%2C+Ludwig%2C+1881-1973%22">Von Mises, Ludwig, 1881-1973</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+equivalence%22">Mathematical equivalence</searchLink><br /><searchLink fieldCode="DE" term="%22Stochastic+processes%22">Stochastic processes</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Richard von Mises was the first to provide a rigorous definition of randomness for infinite binary sequences, taken to represent indefinitely long sequences of experimental outcomes or indefinitely large (ordered) population samples. According to von Mises, a sequence is random if, within it, the relative frequencies of 0 and 1 each converge to a finite limit, and these limiting relative frequencies are invariant under a class of transformations that he called selection rules. While the notion of randomness defined by von Mises is known to have some serious limitations, his theory was pivotal to the development of algorithmic randomness: a branch of computability theory that provides the now-standard approach to defining randomness for individual mathematical objects. The purpose of this article is to call attention to the fact that, despite its flaws, one of the core ideas behind von Mises' account of randomness also underlies much of the theory of algorithmic randomness. In particular, we bring together and generalize a number of little-known results, proving that, for a broad class of probability measures, several canonical algorithmic randomness notions are characterizable in terms of invariance: i.e. in terms of the preservation, or the stable satisfaction, of various natural properties under a class of transformations that can be seen as a generalization of von Mises' selection rules. Many of the properties in question are usually described as 'minimal randomness properties': they are not in themselves sufficient for randomness, but they are often taken to be necessary (or at least desirable) for it. From this perspective, our results establish that algorithmic randomness coincides with the stable satisfaction of various minimal randomness properties (including the existence of limiting relative frequencies, as in von Mises' original account). [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA 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=190650841 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1093/logcom/exae083 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 31 StartPage: 1 Subjects: – SubjectFull: Algorithmic randomness Type: general – SubjectFull: Probability measures Type: general – SubjectFull: Mathematical symmetry Type: general – SubjectFull: Binary sequences Type: general – SubjectFull: Von Mises, Ludwig, 1881-1973 Type: general – SubjectFull: Mathematical equivalence Type: general – SubjectFull: Stochastic processes Type: general Titles: – TitleFull: Randomness and invariance. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Persiau, Floris – PersonEntity: Name: NameFull: Blando, Francesca Zaffora IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 12 Text: Dec2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 0955792X Numbering: – Type: volume Value: 35 – Type: issue Value: 8 Titles: – TitleFull: Journal of Logic & Computation Type: main |
| ResultId | 1 |
