Martingales in the Study of Randomness

Martingales played an important role in the study of randomness in the twentieth century. In the 1930s, Jean Ville used martingales to improve Richard von Mises’s and Abraham Wald’s concept of an infinite random sequence, or collective. After the development of algorithmic randomness by Andrei Kolmogorov, Ray Solomonoff, Gregory Chaitin, and Per Martin-Löf in the 1960s, Claus-Peter Schnorr developed Ville’s concept in this new context. Along with Schnorr, Leonid Levin was a key figure in the development in the 1970s. While Schnorr worked with algorithmic martingales and supermartingales, Levin worked with the closely related concept of a semimeasure. In order to characterize the randomness of an infinite sequence in terms of the complexity of its prefixes, they introduced new ways of measuring complexity: monotone complexity (Schnorr and Levin) and prefix complexity (Levin and Chaitin).