The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: comparing two randomizers
Replies: 5   Last Post: Oct 11, 2007 12:42 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Ben Rudiak-Gould

Posts: 210
Registered: 2/2/05
Re: comparing two randomizers
Posted: Oct 11, 2007 12:42 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Randomness, like probability, has many inequivalent definitions, none of
which is entirely satisfactory. Galathaea is talking about Kolmogorov
complexity, aka algorithmic information content, aka compressibility, where
a string is considered random if the shortest program that prints the string
is longer than the string itself. Obviously any long string of bits produced
by a short program is not random in this sense. But programs are known
(pseudorandom generators) which produce strings that appear to be random,
even though they're not; that is, there's no known general way of detecting
that they're compressible unless someone reveals the algorithm+input to you.
It's because of this that cryptography is possible, but no one knows why
it's true, or even whether it really is true. Of course this also casts
doubt on the idea that there are any sources of true randomness: maybe
radioactive decays would be easy to predict if we just knew the right formula.

BrainDumb wrote:
> At, author claims 'true random numbers to anyone'. From
> reading a few sources,
> 1. I understood it's impossible. Is it true?

I dunno. I have a hard time understanding who would use this service. You
have to be pretty paranoid to believe that /dev/urandom isn't good enough,
and anyone that paranoid isn't going to trust a third party to produce their
randomness. There's no known test you can perform on the output to
distinguish true randomness from a good pseudorandom generator. I guess a
sophisticated paranoiac could use bits from this site as one source for
their local entropy pool, but 9 out of 10 cryptologists agree that you
should just use /dev/urandom.

> 3. If indeed true random was possible than I couldn't say this
> algorithm was better than another. In other words, there is no degree
> of quality once true randomness is achieved?

I suppose so, by definition. It's like saying there are no degrees of
quality once perfection is achieved.

> 4. We are told (on wikepedia) that expansion of Pi produces random
> digits. Yet there are simple series for Pi. A few years ago, a bunch
> of mathematicians produced a formula that calculates any digit of Pi,
> without calculating previous ones.

The digits of pi seem to be good pseudorandom numbers. If you start at the
beginning you always get the same digits, but that's true of any
pseudorandom generator if you always start with the same seed. You could
take the seed of a pi-based generator to be the starting digit. But
calculating digits of pi is very slow and there are faster pseudorandom
generators that work just as well. The world record for pi seem to be around
a trillion hex digits, which took CPU-years of computation on a
supercomputer with terabytes of RAM; other algorithms can produce that many
high-quality pseudorandom digits in a CPU-hour or less on an ordinary
desktop machine.

> a. If numbers after decimal point are random, why are we able to
> tell a digit with 100% accuracy.

That's a deep philosophical question. You may wish to meditate on this koan
for a while:

-- Ben

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.