[Openmcl-devel] random statistical properties and period?

[Gary Byers]

It's a Linear Congruential Generator.  "The literature" (e.g., Google, Wikipedia)
could probably describe the statistical properties of the algorithm better than I
could; a quick summary of that literature (paraphrased slightly) is:

a: Linear Congruential Generators suck!
b: No, they don't.
a: Yes, they do.
b: Do not!
a: Do too!

As you can see, there's quite a lively debate surrounding this issue.
(Actually, I think that the debate has to do with whether or not LCG's
are "good enough"; I think that there's general agreement that they can
have undesirable properties.)

I've seen visual aids suggesting that LCGs are prone to temporal
clustering effects (that a lot of sequentially generated values or
short sequences of those values share common bits or fall into
clustered ranges, but whether this is true and the degree to which
it is true may depend on the moduli involved (e.g., (RANDOM m) might
show clustering, (RANDOM n) might not.  My understanding of the issue
is that other algorithms are more likely to provide statistically random
distributions.

The way that it's implemented, the generator cycles (pseudo-)randomly
through values in the range 1..2^31-1, so if this were C we'd say that
its period was 2^31-2.  It's lisp (not C), and RANDOM may call the
underlying generator multiple times per (RANDOM N) call; the period of
(RANDOM N) depends on N for this and other reasons and can be more or
less than 2^31-2.

;;; Based on a similar function used in email by Bernd Beuster
(defun random-run-length (n  &optional (print t))
    (loop with start fixnum = (random n)
       for current fixnum = (random n)
       for i fixnum from 1
       until (= current start)
       finally (return i)
       do (when (and print (zerop (mod i 10000000))) (print i))))



On Wed, 6 May 2009, Raffael Cavallaro wrote:

> What are the statistical properties and period of CCL's implementation
> of random?
>
> regards,
>
> Ralph
>
>
>
> Raffael Cavallaro, Ph.D.
> raffaelcavallaro at mac.com
>
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>