Chapter 1

Introduction

The “question of randomness” has been puzzling thinkers for ages. Aspects of this

question range from philosophical doubts regarding the existence of randomness (in

the world) and reflections on the meaning of randomness (in our thinking) to technical

questions regarding the measuring of randomness. Among many other things, the

second half of the twentieth century has witnessed the development of three theories

of randomness, which address different aspects of the foregoing question.

The first theory (cf., [16]), initiated by Shannon [63], views randomness as rep-

resenting uncertainty, which in turn is modeled by a probability distribution on the

possible values of the missing data. Indeed, Shannon’s Information Theory is rooted

in probability theory. Information Theory focuses on distributions that are not per-

fectly random (i.e., encode information in a redundant manner), and characterizes

perfect randomness as the extreme case in which the uncertainty is maximized (i.e.,

in this case there is no redundancy at all). Thus, perfect randomness is associated

with a unique distribution– the uniform one. In particular, by definition, one cannot

(deterministically) generate such perfect random strings from shorter random seeds.

The second theory (cf., [41, 42]), initiated by Solomonoff [64], Kolmogorov [38],

and Chaitin [14], views randomness as representing the lack of structure, which in

turn is reflected in the length of the most succinct (effective) description of the object.

The notion of a succinct and effective description refers to a process that transforms

the succinct description to an explicit one. Indeed, this theory of randomness is

rooted in computability theory and specifically in the notion of a universal language

(equiv., universal machine or computing device). It measures the randomness (or

complexity) of objects in terms of the shortest program (for a fixed universal ma-

chine) that generates the object.1 Like Shannon’s theory, Kolmogorov Complexity

is quantitative and perfect random objects appear as an extreme case. However,

following Kolmogorov’s approach one may say that a single object, rather than a

distribution over objects, is perfectly random. Still, by definition, one cannot (de-

terministically) generate strings of high Kolmogorov Complexity from short random

seeds.

1We

mention that Kolmogorov’s approach is inherently intractable (i.e., Kolmogorov Complexity

is uncomputable).

1

http://dx.doi.org/10.1090/ulect/055/01