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
Previous Page Next Page