========================================================================
Now we are going to switch gears a little and see if we can apply our
intuition to investigate what we might expect to observe as the outcome
of a purely random process such as flipping a fair coin. One of the
greatest successes of algorithmic information theory was to provide
the first intrinsic definition of a random number. To illustrate,
suppose that you are flipping a fair coin and recording a 1 for heads
and a 0 for tails. Now consider the following two potential
outcomes:
(A) 0101010101010101010101010101010101010101010101010101010101010101
(B) 1110101010010010101001010011000111100111100110011111000011010011
and try to imagine yourself flipping a coin and writing down the sequence
term by term. Would either of the two results be surprising in any way?
Or, suppose instead that you did not see the coin being tossed. Someone
else claimed to have tossed a coin 64 times and then showed you the
result. Would either result make you suspicious about the fairness of
the coin used or perhaps even about the integrity of the person who
showed you the result?
I think practically everyone would be surprised or suspicious to see
the first sequence since we usually do not expect such a regular
pattern to result from a random process. The second sequence probably
would not be surprising since there is no apparent pattern (in fact,
the second sequence was actually obtained by flipping a coin 64 times).
But perhaps the biggest surprise of all would be to learn that
probability theory provides no justification for what seems to be a
perfectly reasonable conclusion, namely that the first sequence is
unlikely to result from the tossing of a fair coin. In fact, I have
presented this little scenario to a number of individuals and have
found that those familiar with probability theory are likely to
respond something to the effect that although they probably would be
surprised to see the first sequence they really shouldn't be since
the probability of the first sequence occurring is exactly the same
(1 in 2^64) as the probability of obtaining the second sequence.
In fact, all of the 2^64 possible sequences have identical
probabilities of occurring when a fair coin is tossed 64 times
in a row. Some may further argue that the presence of a pattern
in the first sequence is really of no significance at all, indicating
only the human predilection for finding patterns in things.
What we learn from the above considerations is that if a number is
defined to be random in view of the process by which the number is
produced, then an obviously ordered result such as the first sequence
above must be considered random since the random process of coin
flipping produces that result with a probability equal to that of any
other specific sequence. In the words of Gregory Chaitin "The conclusion
is singularly unhelpful in distinguishing the random from the orderly.
Clearly a more sensible definition of randomness is required, one that
does not contradict the intuitive concept of a 'patternless' number."
(Chaitin, 1975).
As might be expected from the above, the "more sensible definition
of randomness" comes from algorithmic information theory where a
random number is defined to be one that is incompressible, i.e. one
that has maximal algorithmic complexity. This definition is intrinsic,
i.e. it depends solely upon the "structure" of the number and is
completely independent of the process (random or deterministic) that
produced that number. Obviously, this may lead to some confusion since
the word "random" in random process has a different meaning from
algorithmic randomness. For this reason it is a good practice
(followed by most authors) to refer to random processes as stochastic
processes so that random will always have its algorithmic meaning.
Thus, algorithmic information theory rescues our intuitive notion of
order. The first sequence above is ordered because it is highly
compressible, no matter what process happened to produce the number.
But what about our intuitive feeling that the first sequence above is
unlikely to be the result of the stochastic process of flipping a
fair coin? Actually, this notion is very closely tied to the
algorithmic concepts of order and randomness. Instead of comparing
probabilities of specific sequences one instead discusses sequences
according to whether or not they are "typical" for a particular
stochastic process. For the stochastic process of flipping a fair
coin, incompressible sequences are typical, highly compressible
sequences are atypical. Thus, our surprise at seeing an orderly
sequence of heads and tails is vindicated since any orderly sequence
is atypical for this stochastic process.
That incompressible sequences are typical for stochastic processes
such as coin tossing can be established by means of a simple counting
argument (see Casti (1990) and Li and Vitanyi (1993) for details).
The results from the counting argument are conveniently presented by
introducing so-called c-incompressibility. A sequence is said to be
c-incompressible if its compressed length is greater than or equal
to n-c where n is the length of the uncompressed string. In other
words, if the length of the string is 64 (as in the examples above)
then all strings that can be compressed to a length of 60 or
larger would be 4-incompressible. Note this is *all* strings so
that, for example, a 5-incompressible string would also be
4-incompressible etc. Based on the counting argument mentioned
above it turns out that at least half of all the strings are
1-incompressible, at least 3/4's are 2-incompressible, at least
7/8's are 3-incompressible etc. Generalizing this, we can say that
at least [1 - (1/2)^c] of all the 2^n possible sequences of length
n are c-incompressible.
It is probably obvious that the "amount of compressibility", as we
usually think of it, depends on both c and the length of the string n.
For this reason we define the % compressibility as follows: %C=[c/n]*100.
To illustrate, for n = 100, a 10-incompressible string can be compressed
by no more than 10% of its original length. Now, using the ideas in
the previous paragraph we see that about 99.9% of all possible strings
of length n = 100 cannot be compressed by more than 10%. For the case
with n = 64, as in our example strings above, about 99.9% of all
strings cannot be compressed by more than 16% and about 99.99999998%
cannot be compressed by more than 50%.