From: Caleb Clausen <vikkous@...>
Date: 2010-04-12T10:07:32+09:00
Subject: [ruby-core:29465] Re: [RubySpec #3128] Randomness specs

On 4/11/10, Marc-Andre Lafortune <ruby-core-mailing-list@marc-andre.ca> wrote:
> Hi,
>
> On Sun, Apr 11, 2010 at 1:30 PM, Caleb Clausen <vikkous@gmail.com> wrote:
>> I find this troubling, since it could imply that the random number
>> generator obeys the mythical law of averages. You know better, I'm
>> sure, but others may not. A written standard needs to be very clear
>> about this, and use the appropriate statistical language.
>
> If I knew better, I would probably refer to a known statistical test :-)

Yeah, me too.
The appropriate language should be something like:

After M>>N iterations, the probability that all integers in the range
0...N have been seen should be [[some number only slightly smaller
than one, calculated from M and N, exact formula not clear to me right
now]].

> I just meant that rubinius' implementation is such that Kernel.rand(1
> << 64) will never return any value greater than 1 << 31, which I find
> troubling.

Yeah, that's clearly wrong.

>> 5) could be interpreted 2 ways, depending on the meaning of the
>> ambiguous term 'platform'.
>
> Indeed, sorry about the poor wording. I meant in the stronger sense,
> i.e. on all implementations and all platforms (your 5b)

I think we're still not reading from the same page on this... :)

Reading back over your message, it's clear that you meant from 5)
something like: the Random class (and Kernel#rand) must behave exactly
like MRI's Random under all circumstances. That's far too stringent of
a requirement in my opinion.

What I originally thought you meant, (maybe Nobu too) was that a
particular implementation's Random should be consistent with itself;
it should always return the same sequence given the same seed
regardless of what OS (or JVM, say) it's running under. Thus, JRuby's
Random should return the same random sequence whether its running
under windows, linux, sunos, blackstone, whatever. But it need not
return the same sequence as MRI on those same platforms.

> So, what should apply to the Ruby language?

Here's my opinion:

Random numbers should appear to be random, given some reasonable
minimum set of TBD randomness tests. It's easily possible to get too
crazy with the RNG tests. (The most complete test for random numbers I
have seen is diehard [1] (written in fortran, and doesn't give clear
pass/fail result, unfortunately.... which is a problem with RNG tests
generally). [2] is also somewhat helpful.) This is what you're driving
at with 0) 1) and 2).

[2] suggests chi-squared tests, which is probably reasonable. (I don't
actually understand the math behind this... also this test also does
not give a clear pass/fail result...)

In addition, there should probably be some language like this:

  Random MUST NOT (SHOULD NOT?) use a known weak random number
generator, such as the linear congruential generator.
  Random SHOULD use Mersenne Twister, since this is simple to
implement and the state of the art in PRNGs at the time of writing.
Random MAY use a better algorithm than MT if such an algorithm is
invented in the future.


[1] ftp://stat.fsu.edu/pub/diehard (not working ATM)
[2] http://burtleburtle.net/bob/rand/testsfor.html