Randomness of a bit string

Here's a short article I wrote for sci.crypt aboout "randomness" of a
bit string and the Kolmogorov-Chaitin definition that a string is
random if and only if it has no shorter description than itself.

This has some fascinating tie-ins to "cryptoregular" strings, which
are strings which appear to be "regular" (a variant of randomness,
meaning all digits are equally represented...high entropy) but which,
with the right transformation, suddenly lose their regularity. 

(For you practical engineering folks, noise sources and other physical
randomness sources will in most cases be enough, even if the
randomness can never be "proved.")

--Tim May


Newsgroups: sci.crypt
From: tcmay@netcom.com (Timothy C. May)
Subject: Re: Randomness of a bit string
Message-ID: <tcmayCK5CtF.23H@netcom.com>
Date: Mon, 24 Jan 1994 18:32:03 GMT

Bruce Grant (bgrant@umcc.umcc.umich.edu) wrote:
: The usefulness of a one-time pad seems to hinge on whether the sequence
: of key bits is really random.  Could someone post a short, not too
: technical definition of randomness of a bit string?  In particular, is
: this a mathematical property, or just a general measure of whether the
: string is "predictable"?  Does it depend on the nature of the cryptanalyst
: or only on the string of bits?  (In other words, if the key is based on
: an Albanian translation of "Mary had a little lamb" is it random if you
: don't know Albanian?)

: Could a program test a key for randomness, or is this meaningless?

A fascinating question! The answer lies at the heart of what we mean
by randomness, complexity, predictability, regularity, and falls into
the field of Kolmogorov-Chaitin complexity, or algorithmic information
theory. Also called "descriptive complexity."

Basic definition: A random string has no shorter description than
itself. That is, it is incompressible.

(Practically, we know "random strings" won't compress much...sometimes
a compressor will shorten them, sometimes it will lengthen them. The
notion above, that random strings will not compress, is very general
and applies in the limit, not for some particular instance of a
string--and some particular instance, e.g., "1 0 0 0 1 1 0" will of
course have a good chance of having some particular compressions, some
short description.)

One consequence is "regularity": all digits of a base will be equally
represented in the limit. Another consequence, as noted in one of the
other followups to this question, is unpredictability of the next
element or bit in a sequence. (Predictability of bits would imply a
compression.)

Cryptography is an interesting situtation. Charles Bennett talks about
"cryptoregular" strings in a paper in the "Physics of Computation"
Proceedings (1992, IEEE Press). A cryptoregular string _appears_ to
have high entropy ("maximum randomness") and regularity (all symbols
equally represented), and thus to be "random." But application of the
_key_ will show the string is actually low entropy ("Mary had a little
lamb, it's fleece was white as snow...") and is very compressible (the
name of the song is the compressed version, for example).

Good cryptography means cryptoregular strings.

A fascinating discovery by Chaitin and others (Kolmogorov, Solomnoff,
Martin-Lof, Levin all worked in this area) is that one can never prove
a given sequence or string is "random." As in some diabolically clever
IQ test, an apparently random sequence may have some shorter
description, or compression, that means it does not fit this
definition of randomness.

Having said this, it is clear that for practical purposes, many
sources used to generate "random numbers," e.g., noise diodes, alpha
particles, tosses of a coin, etc., are "effectively random" (don't ask
me to define this!) in that no compression/prediction will ever be
done, though we can never be absolutely certain one does not exist!

A nice book on this stuff just came out: "An Introduction to
Kolmogorov Complexity and Its Applications," by Li and Vitanyi, 1993,
Springer-Verlag. Cryptography per se is not mentioned (a disappointing
lapse), but the ideas are widely applicable.

--Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power:2**859433 | Public Key: PGP and MailSafe available.

Tim May writes:

> A fascinating discovery by Chaitin and others (Kolmogorov, Solomnoff,
> Martin-Lof, Levin all worked in this area) is that one can never prove
> a given sequence or string is "random."

I believe this is overstating the case.  The only theorem along these
lines that I saw in Li and Vitanyi's book was that, for any logical
theory, there are at most a FINITE number of strings that can be proven
random.  The upper bound on the number of strings that can be proven
random is quite large, by the way -- it's larger than 2^n, where
n is the minimum number of bits needed to represent the logical theory.
Thus, although no algorithm can tell you, for all strings x, whether or
not x is random, it may be possible to prove a few particular strings
random (with respect to a given encoding of algorithms).

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

Kevin Van Horn writes:

> Tim May writes:
> 
> > A fascinating discovery by Chaitin and others (Kolmogorov, Solomnoff,
> > Martin-Lof, Levin all worked in this area) is that one can never prove
> > a given sequence or string is "random."
> 
> I believe this is overstating the case.  The only theorem along these
> lines that I saw in Li and Vitanyi's book was that, for any logical
> theory, there are at most a FINITE number of strings that can be proven
> random.  The upper bound on the number of strings that can be proven
> random is quite large, by the way -- it's larger than 2^n, where
> n is the minimum number of bits needed to represent the logical theory.
> Thus, although no algorithm can tell you, for all strings x, whether or
> not x is random, it may be possible to prove a few particular strings
> random (with respect to a given encoding of algorithms).

I don't believe this is overstating the case at all. To quote Gregory
Chaitin, from a context I cannot do justice here: "...leads to the
demonstration that a specific number cannot be proved random."
("Information, Randomness, and Incompleteness: Papers on Algortithmic
Information Theory," Second Edition, 1993)

To see this another way, suppose an algorithm existed to always know
if a given number is "random" or not. Then application of this
algorithm to the natural numbers would presumably find the "smallest
random number," such as "729." (An inside joke.) But this smallest
random number would itself be intensely interesting and hardly random.
And so on, a la the Berry Paradox and other well-know cousins of
Godel's Theorem.

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.

(Is it cheating to invoke other systems, books, etc. in the
definition? Hardly. Cryptographers do it all the time. The mass of
planet motion observation data certainly _looked_ random to ancient
astronomers, until Kepler found his amazing compression of the data.)

There is a mass of stuff here, and much room for us all getting
tangled up in what randomness really means, what algorithms are,
formal definitions (with reference to Turing machines and whether they
halt or not, etc.), and so on. I urge interested readers to read
Chaitin's papers, which are focused on issues of randomness, and also
the Li and Vitanyi book.

I stand by my point that no number or sequence can be proved to be random.


--Tim May




-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power:2**859433 | Public Key: PGP and MailSafe available.

Timothy C. May says:
> 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.
> 
> (Is it cheating to invoke other systems, books, etc. in the
> definition? Hardly.

Wrong, Tim. An algorithm must be self contained. If you have to refer
to Chaitin's book in the algorithm, you must include it in the
algorithm. For a proof, consider the following notion: you have a
large number that you THINK is incompressable. Write it down in the
"little book o' random numbers", now refer to it as the third number
in the book. Obviously, of course, this is bullshit -- if you
transmitted it to someone that way you would have to send the book,
too. This is unlike your earlier (correct) proof that you can't show a
number is random because where there an algorithm you could order the
random numbers and the first would no longer be random, because the
algorithm *is* self contained in that case.

> The mass of
> planet motion observation data certainly _looked_ random to ancient
> astronomers, until Kepler found his amazing compression of the data.)

Its correct that Kepler compressed the string, but incorrect to note
that having written the numbers in a book had anything to do with it.

Perry

> From: tcmay@netcom.com (Timothy C. May)
> I don't believe this is overstating the case at all. To quote Gregory
> Chaitin, from a context I cannot do justice here: "...leads to the
> demonstration that a specific number cannot be proved random."

Perhaps the context is relevant.  Chaitin's `omega', for example, is
Kolmogorov random (too bad!).  (Omega is the sum over all x of m(x),
where m(x) is the Solomonoff-Levin distribution.)

> To see this another way, suppose an algorithm existed to always know
> if a given number is "random" or not. Then application of this
> algorithm to the natural numbers would presumably find the "smallest
> random number," such as "729." (An inside joke.) But this smallest
> random number would itself be intensely interesting and hardly random.

This is an informal argument, using an informal definition of
randomness.  Presumably in this discussion we could standardize
on Kolmogorov randomness, to which definition Berry's paradox
does not apply.

> --Tim May

   Eli   ebrandt@jarthur.claremont.edu

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 |

Timothy C. May says:
> Here's a short article I wrote for sci.crypt aboout "randomness" of a
> bit string and the Kolmogorov-Chaitin definition that a string is
> random if and only if it has no shorter description than itself.

With respect, Tim, this definition is insufficient. For cryptographic
purposes, a string must not merely be incompressible but also unknown.
One can imagine things that are uncontrollable and incompressable but
well known -- such as, say the least signifcant bits in the payoffs on
winning horses at some race track.

Perry

There seems to be a misinterpretation of the point I was making about
randomness and how no number (or sequence) can be _proved_ to be random.

> This has some fascinating tie-ins to "cryptoregular" strings, which
> are strings which appear to be "regular" (a variant of randomness,
> meaning all digits are equally represented...high entropy) but which,
> with the right transformation, suddenly lose their regularity. 
...
> Basic definition: A random string has no shorter description than
> itself. That is, it is incompressible.
...

> A fascinating discovery by Chaitin and others (Kolmogorov, Solomnoff,
> Martin-Lof, Levin all worked in this area) is that one can never prove
> a given sequence or string is "random." As in some diabolically clever
> IQ test, an apparently random sequence may have some shorter
> description, or compression, that means it does not fit this
> definition of randomness.

The point here is for a number or sequence which is _given_, just
presented, as in:

"Is the sequence 100010001010110010101 random?"

Or,

"Is the number 9045886804 random?"

Variants of this question come up all the time, as in predicting the
next term of a sequence, trying to determine if a sequence of
characters is likely to be just noise or is instead likely to be a
message, and in issues of whether data is maximally compressed or can
be compressed still further.

These numbers are "found objects" in the sense that one generally has
no idea what "model" or "theory" generated them.

Someone looking at the first example, 100010001010110010101, might
subject it to all kinds of tests:

-visual inspection to see if it's some "obvious" number (such as
"1010101010101010" would be, or "01011101110111" might be)

-statistical tests, to see if it deviates "significantly" from the
expected pattern of random numbers (regular distribution of digits, of
pairs, triples, quadruples, etc.). The usual arsenal of entropy
measurements, chi-square tests, null hypothesis testing, etc.

-other tests to see if the number is related to other known numbers,
which could be things like the day of the year, the digits of pi, the
phone number of whoever generated the number, etc.

-other tests and guesses that cryptanalysts and puzzle-solvers are
familiar with

A plausible result for someone to announce, after such a series of
tests, is "I can't find any patterns, and the distribution of digits
falls within expected ranges. We've compared the number against the
suspect's various numbers and can find no linkages. It looks pretty
random to us." (By "random" he essentially means "like the result of a
sequence of coin tosses." Fair coin, of course.)

But can he ever say "I can prove the number is random"? No. There's
always some chance an even-cleverer puzzle solver will find the
pattern, the key that unlocks the randomness. For example, most
ciphertexts pass nearly all statistical tests for randomness, "look"
random, and even _act_ like random numbers (recall the Blum-Blum-Shub
pseudorandom number generator and how good it is). But simple
application of the key turns the seemingly random
"100010001010110010101" into "ATTACK."

Let's look at the second example. Is the number "9045886804" random or
not? And can we _prove_ it's random? (If you're worred that these
numbers are somehow too small, don't worry. The same reasoning applies
to any number or sequence one might encounter, including short numbers
and multi-page numbers or sequences (such as PGP might generate)).

The cryptanalyst or problem-solver looks for the patterns, the
statistical distributions and entropies, and _any other_ links he can
think of. That is, his "models" for the generator of this number are
not known to him, but he may make some guesses based on the owner of
the number, the score in the SuperBowl, the age of Bill Clinton, etc.
That is, he'll look to see if the number is some sort of simple cipher
or transpostion based on one of the "unrandom" numbers around him.

To cut to the chase, can he ever "prove" the number is random? Can he
even claim that the generator of the number "must have" used a process
that is commonly used to generate numbers with a good approximation to
a random process (flippin coins, alpha counts, etc.)?

Suppose he declares to his boss, Admiral Inman, that he has "proved"
the number is "random." Inman says to him: "This post was written by
this trouble-maker Tim May, who even gives his phone number in every
post he writes. What happens if we reverse the digits of his number?
408-688-5409 turns into 9045886804! Some "random" number! Clean out
your desk tonight."

Now is it kosher to take the "theory" of my phone number and allow it
to be included in the analysis of wheter a number is random or not? Of
course it is! In the real world, this is what we mean by randomness
and predictabilty, whether we can find patterns and structure. And
this is what cryptanalysts really do, and what good password-guessing
programs do: they take account owner information such as name,
spouse's name, pet's name, birthdate, and any other information they
can scrounge about an account owner and then run permuations and hope
for the best. Some percentage of the time, the passwords are
"guessed," meaning that they were not very random at all.

(This was the point I was making about famous numbers (like "729"),
paradoxes (there are no "uninteresting" numbers, because the smallest
"uninteresting" number is automatically interesting, and in fact is
has a short description), and the number listed in Chaitin's book. I
hope this explanation here makes it a bit clearer.)

In this real world of trying to break cyphers, all is fair. All models
may be considered, though not all models can be (e.g., one would not
try applying the phone number of Chester Umbizi in Nairobi, Kenya at
random!).

No number can be proved to have no shorter description than itself.
And as various shorter descriptions are found, with whatevr effort it
takes, it cannot be proved that the description is the shortest that
will ever be found. It may be strongly susepected that no shorter
description exists. In fact, most numbers are incompressible, but a
simple counting argument, in any theory. (For example, of the
100-binary-digits, not many of them have 50-digit compressions, and
even fewer have 10-digit descriptions. Work out the numbers.)


So, if someone tells you they've "proved" a particular number is
random, just smile.

--Tim May

--




-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power:2**859433 | Public Key: PGP and MailSafe available.

Thanks to Tim May for his *excellent* tutorial on randomness, which
can be compressed into a single sentence:

"Randomness is in the eye of the beholder."

:-)

Phil