Randomness and invariance

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).