Re: best approach to generate random number in java

From: Alex Hunsley (lard_at_tardis.ed.ac.molar.uk)
Date: 10/15/04 

Date: Fri, 15 Oct 2004 10:34:54 +0100

Paul Lutus wrote:
> Alex Hunsley wrote:
>
> / ...
>
>
>>I have a theorem: (if it can be called that)
>>
>> Truly unpredictable sequences of numbers can be produced
>> by algorithmic means,
>
>
> Umm, IMHO no. Because if one has access to the algorithm, and if one sets it
> to the same initial state, it will produce the same sequence. Therefore the
> original algorithm can be used to "predict" the entire sequence.

There is a difference between the determinism of an algorithm and the
predictability of the distribution of the numbers it produces...

Also, I am assuming the user does not know where the starting point in
the sequence is. The user does not know the seed - and if they do not
know this, then it doesn't matter that they know it is the pi RNG.
(Of course, the above only truly holds if the starting position could be
anywhere in pi, despite the fact that the further along the starting
postiion, the s l o w e r the algorithm would run. But I am talking of
theoretics here, not practicalities.)

>
> If one does not have access to the original algorithm, one might embark on a
> quest to locate the algorithm, using, say, a future quantum computer
> capable of producing algorithms for supplied number sequences.

If you don't know the starting point in the sequence, knowing the
algorithm wouldn't matter - you have no idea when the sequence you see
will diverge from what might look like a 'familiar' sequence like
14159265358979.

> Then, if the quantum computer approach were to fail, strongly implying that
> the number sequence was in fact nondeterministic, one could fairly say it
> was unpredictable and very complex, e.g. using the classical definition
> that the number sequence is itself the shortest expression of the
> information it contained.

Unfortunately, this scheme wouldn't always work. For the computer to
guess the pi algorithm, you would have to

a) put in all the decimal places of pi (!)
b) leave the computer to run forever (!)

These requirements scupper the plan.... no matter how many qubits you
put in a quantuum computer, infinity still poses a problem.

There's no reason that the scheme shouldn't work for finite sequences
though.

>> but the runtime needed to produce
>> successive numbers ramps up (possibly exponentially).
>
>
> I think there is an interesting (and recognized) point after which the
> numbers themselves are the shortest form the information can take. That is
> truly unpredictable.

Yup, this is a good point. Despite its seeming randomness, the places of
pi are deterministic, and reproducable with a very short algorithm, so
in that sense the places of pi are not utterly random. Which is why it's
so fascinating.
A well known rough test of how random information is: zip it up in
winzip. Now, I wonder what compression you get if you zip up a text file
containing places of pi?

It reminds me of the whole mandelbrot set thang: how such an amazing
structure is encoding by an eqn. as simple as z |-> z^2 + c (and knowing
how complex numbers work).
((I have started reading "The Road to Reality" by Roger Penrose which
touches on this theme at the beginning. Highly recommended book, if all
the maths doesn't put a spade in your head.))

Another digression:
I wonder what percentage of all possible permutations of information are
truly random and non-compressible?
For example, generate all possible binary strings of length 100. (So
you'd have 2^100 strings to test.) For each string, see how compressible
it is. What percentage of them will be not compressible at all? Will
this remain constant for different sizes of strings? (answer: no, I feel.)

alex

Relevant Pages

  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)
  • Re: an true information theory
    ... > outputs, and figures out that the algorithm must be A1, there ... > there is an infinite number of stages n such that P's guess at ... > sequence of algorithms, strike off every algorithm that appears ... I've read that quantum computing may improve tractability but ...
    (sci.math)
  • Re: creating an (inefficent) alternating regular expression from a list of options
    ... specify a list of strings and have them converted to a regular ... A Perl module which does an aggressively optimizing job of this is ... given an input sequence I and a set of ... the algorithm should remove overlapping subsequences ...
    (comp.lang.python)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... any other similarly sized non-overlapping stretch of numbers in pi. ... "calculation" or algorithm that produces pi every time is the means by ... the sequence of pi as well as e and *simple* repetitive ... number of binary strings with an HD of 23 from a string of 100 ...
    (talk.origins)
  • Re: best approach to generate random number in java
    ... Because if one has access to the algorithm, ... >> it to the same initial state, it will produce the same sequence. ... Well, infinite children, and infinite play. ... >> Then, if the quantum computer approach were to fail, strongly implying ...
    (comp.lang.java.programmer)