Randomness of a bit string

[kevin@axon.cs.byu.edu (Kevin Vanhorn)]

Continuing the discussion on whether there may exist a few random strings
that can be proven random...

Tim May writes:

> To see this another way, suppose an algorithm existed to always know
> if a given number is "random" or not.  [Paradoxes follow]

But that's not what I was talking about; I specifically acknowledged
that there was no such algorithm that ALWAYS gives you the
answer.  But even in the absence of a general algorithm to decide a
problem, it may be possible to decide some specific instances.  For
example, a basic result of computability theory is that there is
no algorithm that will, for any program P and input x, tell you if
P eventually halts on input x.  Yet there are many SPECIFIC instances
of programs P and inputs x for which it has been proven that P halts on
input x; this is what the whole business of formal proofs of program
correctness is about.

> If someone claims they can "prove" the sequence "0
> 1101100110111100010" is really random, ask them _how_. Ask them if the
> compression "Chaitin 27," meaning the example number given on page 27
> of Chaitin's book is not that same number, making it hardly random.

This argument is invalid.  To see why, let's review the definition of
a random string.  Randomness is defined in terms of Kolmogorov
complexity, which is defined relative to any universal function U.  (A
universal function U takes as input an encoding of a Turing machine T,
together with its input z; its output is undefined if T does not halt
on input z, otherwise its output is the value T outputs on input z.
Each different effective encoding of program-input pairs defines a
different universal function.)  The Kolmogorov complexity C_U(x) of a
string x (relative to U) is defined to be the length of the shortest
string y such that U(y) is defined and U(y) = x.  In a sense, it
doesn't matter which universal function you use, since it turns out
that for any two universal functions U and V there exist constants c1
and c2 such that

   C_U(x) <= C_V(x) + c1  for all x, and
   C_V(x) <= C_U(x) + c2  for all x.

A string x is defined to be random (w.r.t. U) if C_U(x) >= x.

Trivially then, the empty string is a random string.  Also, Tim's
example is meaningless, since it does not give an algorithm.
(Caveat: you COULD construct a universal function U that has
Chaitin's book built in to it, but it is certainly NOT the case that
every universal function has this property.)

To prove that a nonempty string x is nonempty, it suffices to prove
that for all strings y shorter than x, either U(y) is undefined
or U(y) != x.  This amounts to proving the output (and halting
behavior) of a finite number of program-input pairs.  For some strings
x and universal functions U this task may be absolutely trivial.  Consider
a Turing machine T that always halts and always outputs the empty
string, regardless of its input.  Let z_1,...,z_m be m arbitrary
strings, where m exceeds the number of strings shorter than x.  It is
straightforward to construct an effective encoding of program-input
pairs for which (T,z_i) is encoded as the i-th bit-string in
lexicographic order.  Suppose that U is the corresponding universal
function, and let y_i be the encoding of the program-input pair
(T,z_i).  Then U(y_i) is the empty string, for all 1 <= i <= m.  Since
the set { y_i : 1 <= i <= m } includes every string shorter than x,
and x is nonempty, we then see that x is random (relative to U.)

-----------------------------------------------------------------------------
Kevin S. Van Horn     | It is the means that determine the ends.
kevin@bert.cs.byu.edu |