Re: best approach to generate random number in java

From: Paul Lutus (nospam_at_nosite.zzz)
Date: 10/15/04 

Date: Fri, 15 Oct 2004 10:22:14 -0700

Alex Hunsley wrote:

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

Yes, true, but the existence of an algorithm that is shorter than the
resulting series does place the series in a different class -- unless, of
course, the algorithm cannot be found. This is how an engineer would say
it, anyway.

> Also, I am assuming the user does not know where the starting point in
> the sequence is.

That does put the question in a different light, unless infinite time is
available to perform tests. Given the latter, one could generate any number
of series and compare using a sliding window approach.

A real mathematician (which I am certainly not) would object on theoretical
grounds that if an algorithm exists that is shorter than the series, it is
child's play to find it. Well, infinite children, and infinite play. :)

/ ...

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

See above, sliding window, infinite analysis time.

>
>> 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 (!)

I agree, and I wasn't thinking of an infinite series above.

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

Yes, quite.

/ ...

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

I have done a lot of this as it turns out. Digits of Pi, e, etc, appear
quite random using this test, assuming the compression schemes are optimal
of course. Near the other end of the spectrum, plain-language text. And at
the far end of the spectrum, political speeches. :)

/ ...

> Another digression:
> I wonder what percentage of all possible permutations of information are
> truly random and non-compressible?

But you used the word "information", so you have, perhaps inadvertently,
undermined your example. The set of stochastic processes is infinite, and
it is possible that the set of orderly proceses is also. Over time, entropy
turns some of the latter into the former. 

-- 
Paul Lutus
http://www.arachnoid.com

Relevant Pages

  • 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: 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: Church-Turing compared to Zuse-Fredkin thesis (two new papers)
    ... I enjoyed thinking more about the consequences of Turing, ... A sequence is said to be computable if it can be computed by a circle-free ... circular if it performs an infinite computation outputting only finitely ... because it can be generated by a shorter algorithm. ...
    (comp.theory)
  • Re: best approach to generate random number in java
    ... > to the same initial state, it will produce the same sequence. ... There is a difference between the determinism of an algorithm and the ... > quest to locate the algorithm, using, say, a future quantum computer ... generate all possible binary strings of length 100. ...
    (comp.lang.java.programmer)
  • Re: Poetential infinity
    ... > represented more formally as discrete infinite sequences. ... If you search Google with terms "potentially infinite" turing machine tap ... for an algorithm has a finiteness requirement. ... "computational method" which abandons the finiteness requirement: ...
    (sci.logic)