Re: entropy of pseudo random number generators

[John Denker <jsd@MONMOUTH.COM>]

> John Denker wrote:
> >
> > I'll bet the output of the pseudo-random number generator (PRNG) on my
> > computer is more random (i.e. passes more tests for randomness) than the
> > output of your Geiger counter.  OTOH people may point out that a PRNG spews
> > out a lot of bits, but not any real entropy.  And they're right.  So let's
> > not talk about PRNGs.

Then at 09:58 AM 3/30/00 -0500, Ludwik Kowalski wrote:
> I think that the "entropy also increases" when your random numbers are
> generated. You can not run a computer without doing this to the universe.
> I am not sure "they are right", unless "spews' means something else.

I was talking about the entropy in the output symbols.

To see what this means, consider a program that spews out a long string of
zeros, nothing but zeros.  The Shannon entropy of the output stream is zero
bits per symbol.  Chaitin's algorithmic complexity of the output stream is
zero bits per symbol.

We agree that the program contributes to the entropy of the universe;  my
point is that none of it is in the output symbols.

Now let's move from zeros to pseudo-random numbers.

If you know the seed, a PRNG has zero entropy per symbol in the output
stream.  You can prove this by running another copy of the PRNG on another
computer (starting from the same seed) and using it to reversibly erase the
first computer's output tape.  You are left with a copy of the seed (which
is bounded), not a copy of the tape (which would be unbounded), proving
that the entropy per tape symbol is zero.  (Contrast this with TRNG output,
which cannot be reversibly erased.)

If you don't know the seed, you won't be able to tell the difference
between a TRNG and a good PRNG unless you watch for an absurdly long
time.  It's rather analogous to a spin-echo system, where your evaluation
of the entropy is contingent on how much you know about how the system was
prepared.