Randomness and Invariance

Abstract: The first (semi-)formal definition of randomness for infinite binary sequences dates back to von Mises’ work in the foundations of probability and statistics. According to von Mises, a sequence is random if, within it, the relative frequencies of 0 and 1 converge to a limit and these limiting relative frequencies are invariant under a class of transformations called selection rules. The randomness notion introduced by von Mises is nowadays widely regarded as being too weak and his account has been supplanted by the theory of algorithmic randomness, which characterizes randomness using the tools of computability theory and measure theory. The goal of this talk is two-fold. First, I will discuss a lesser-known characterization of Schnorr randomness due to Schnorr, which demonstrates that it is possible to obtain a satisfactory randomness notion by defining randomness, analogously to how von Mises did it, in terms of the invariance of limiting relative frequencies. Then, I will discuss how other canonical algorithmic randomness notions are similarly characterizable in terms of the preservation of natural properties under the class of computable measure-preserving transformations. This talk is based on joint work with Floris Persiau.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic