From: tcmay@netcom.com (Timothy C. May)
Date: Mon, 24 Jan 94 19:46:43 PST
To: kevin@axon.cs.byu.edu (Kevin Vanhorn)
Subject: Re: Randomness of a bit string
In-Reply-To: <9401242012.AA29021@axon.cs.byu.edu>
Message-ID: <199401250337.TAA14525@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


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.