View in EDS

Randomness and invariance.

Saved in:

Bibliographic Details
Title:	Randomness and invariance.
Authors:	Persiau, Floris¹ (AUTHOR), Blando, Francesca Zaffora² (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

Description
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]
ISSN:	0955792X
DOI:	10.1093/logcom/exae083