There are two conflicting definitions of randomness being used here.
The purpose of a pseudo-random number generator (PRNG) on a computer
is to provide a sequence of numbers that is statistically
indistinguishable from random noise. Good PRNG cover their range
completely and do not show any obvious patterns in the sequence of
digits. This statistical randomness is different from Chaitin's
informational randomness.
The digits of pi are statistically random, even though they are
completely determined. They could be used as a PRNG, but you would
prefer a faster algorithm than one of the ones that can be used to
generate the digits of pi. These algorithms are much shorter than the
theoretically infinite number of digits of pi that they could generate.
The linear congruential generator that Critchlow describes is quite
short, but generates long streams of numbers before it repeats. So it
is useful for making up seemingly random sentences or pictures or
other objects. This generator shows a streaking pattern if you use it
to choose a pair of numbers as coordinates for where to plot a pixel,
so there are some applications where it would not be considered random
enough, but there are many others where it would be sufficient.
The successive digits of the square root of a prime number can be used
as a PRNG, but when pairs of numbers are used as coordinates for a
plot, they fill the space in a very predictable pattern. Algorithms
like this are called quasi-random number generators. Another example
would be the points on Peano's space-filling curve. For most
applications, this regular, non-overlapping coverage would be
undesirable, but for many Monte Carlo applications, it provides order
N convergence, which is a huge improvement over the order N^2
convergence provided by a purely random sequence or by most PRNG.
-Roger Frye
On Apr 23, 2009, at 1:05 AM, Nicholas Thompson wrote:
Hi, everybody,
Now that the recent burst of metaphysics is completed, I was curious
about your take on the following quote, which is from a footnote in
Dennett's Real Patterns:
"More precisely: 'A series of numbers is random if the smallest
algorithm capable of specifying it to a computer has about the same
number of bits of information as the series itself" (Chaitin, p.
48). This what explalins the fact that the random number generator
built into most computers is not really properly named, since it is
some function describable in a few bits (a littlesubroutine that is
called for some output whenver a program reuires a 'random' number
or series).
So far it all makes sense to me. But now Dennett adds the following
comment:
If I send you the descriptoin of the pseudo-random number generator
on my computer, you can use it to generate exactly the same infinite
series of random-seeming digits.
Now, it seems to me that IF the behavior of a pseudo-random number
generator IS describable in a very few bits ... if it is a SMALL
program ..., then the pattern it generates is also describable with
enormous savings and it is not, by Dennetts definition, anything
like random. It might by mysterious, but no where near RANDOM.
Can anybody help me understand this. (Please try to say something
more helpful than the well-deserved, "Well, why do you THINK they
call it pseudo-random, you dummy?")What DOES a pseudo randomizing
program look like?
Nicholas S. Thompson
Emeritus Professor of Psychology and Ethology,
Clark University ([email protected])
http://home.earthlink.net/~nickthompson/naturaldesigns/
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
