Re: comparing two randomizers

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 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:

http://imgs.xkcd.com/comics/random_number.png

-- Ben
.

Relevant Pages

  • Re: Pi, randomness of numbers?
    ... >> The poster asks about 'randomness'. ... >> as expected for a number formed by adjoining random iid digits. ... proportion of the transcendentals in. ... is uniform on the interval if the d_i are iid uniform on ...
    (sci.math)
  • Re: Randomness from data
    ... >>thus having obtained 'randomness' justified? ... > sampled value using less bits only, even if the phenomena you're sampling is ... which one of the digits x one could justifiably collect ...
    (sci.crypt)
  • Re: Randomness of digits within pi
    ... do not seem to occur as frequent as ... Each of them should only turn up once in one million digits on ... describes results from a number of tests on the randomness ... number and 6 not that lucky. ...
    (sci.math)
  • Re: PI random? Debate running in circles (you try making math jokes)
    ... So, you ask, "Are the digits of Pi randomly distributed ?" ... "Because the notion of randomness invokes the ... Your question about randomness of Pi is no different that the next one ...
    (sci.math)
  • Re: Kolmogorov Complexity - again
    ... becomes less and less relevant as the string continues to ... between the notions of randomness and inductive inference. ... Kolmogorov, Solomonoff, Von Mises, Chaitin, etc. all had the same ... it is quite clear that the choice of UTM only matters in the ...
    (talk.origins)
Loading