Peter Gács
Boston University

May 16, 2008
Elements of Information Theory Workshop
Stanford University

The algorithmic theory of randomness is well developed when the underlying space is the set of finite or infinite sequences and the underlying probability distribution is the uniform distribution or a computable distribution. However, the restriction to computable measures or to discrete sequences seems artificial.

The first attempts to extend this theory were made by Martin-Lof, defining a test for the class of all Bernoulli distributions (later extended by Levin to more general classes). Levin contributed ideas defining randomness tests that contain the measure also as an independent variable. I have taken up these ideas and generalized them to objects more general than just sequences of symbols.

Recent work of Hoyrup and Rojas on uniform tests allows a reconsideration of class tests in the general framework. We show that for a "nice" class C of measures (having a certain constructive orthogonality property), the randomness test of an object with respect to a measure P in C separates into a maximum: max(t_C(x), s_P(x)). Here t_C(x) is the class test, and s_P(x) is a so-called separation test (typically just testing the convergence of the empirical distribution to P). The difficulties of applying the result to the class of ergodic stationary processes will be discussed.