Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: comparing two randomizers
Posted:
Oct 11, 2007 12:42 PM


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 random.org, 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 pibased 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 CPUyears of computation on a supercomputer with terabytes of RAM; other algorithms can produce that many highquality pseudorandom digits in a CPUhour 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:
http://imgs.xkcd.com/comics/random_number.png
 Ben



