Dimension, Pseudorandomness and Extraction of Pseudorandomness

Abstrakt

In this paper we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz.

Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on a distribution is quantitatively equivalent to the notion of dimension we define.

Klíčová slova

• Pseudorandomness
• Dimension
• Martingale
• Unpredictability