Date: Thu, 10 Dec 1998 13:07:23 +0200 (IST)
From: Eli Zaretskii <eliz AT is DOT elta DOT co DOT il>
X-Sender: eliz AT is
To: Kbwms AT aol DOT com
cc: djgpp-workers AT delorie DOT com
Subject: Re: RNG random()
In-Reply-To: <1286efc6.366e7746@aol.com>
Message-ID: <Pine.SUN.3.91.981210130641.2237B-100000@is>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Reply-To: djgpp-workers AT delorie DOT com


On Wed, 9 Dec 1998 Kbwms AT aol DOT com wrote:

> > Is it possible to summarize in a few words what those ``unfavorable
> > properties'' are?
> >
> > If not, just point me to the URL where this paper is available.  Thanks.
> 
> Retrieve his papers via anonymous FTP (faster under AOL) from

After reading this, I'd say that the sentence about ``unfavorable
properties'' of the lagged-Fibonacci generators which therefore
``should be avoided'' is way too strong.  Especially since the paper
then shows that almost every RNG on Earth has similarly bad properties
under some circumstances.

In a nutshell, the paper demonstrates that certain combinations of
random numbers produce multi-dimensional vectors that are very poor
samples of that multi-dimensional space.  One example looks at the
following generator:

	  X(n) = [X(n-24) + X(n-55)] mod 2^e

and shows that the three-dimensional points defined by the random
numbers of the form (X(k), X(k+31), X(k+55)), for every k, lie in only
two parallel planes in the 3D space.  This is indeed a very poor
sampling of the 3D space.

But what does this mean in practice?  For me, it means that a
stochastic program which wants to yield statistically sound results
needs to be run with several different RNGs, and if that's not an
option, to reshuffle n-tuples of random numbers produced by the RNG in
a different manner for each Monte-Carlo run.

I'd assume that somebody who's head and shoulders into the business of
stochastic simulation should already know that.  (And if not, they
surely need to read this paper!)

However, this certainly does NOT mean that we should dismiss `random',
`rand48', or any other widely-used RNG, just because they are all bad
anyway.  On the contrary, we should IMHO try to provide several
different RNGs, so that whoever needs to switch them, could do that.
We also should not stop putting small improvements into the existing
RNGs: even if these improvements do not (and can not) make their
worst-case behavior better, they make them better in other aspects.

Perhaps the following excerpt from the paper is the best summary of
the issue:

   It is not clear how those properties really affect the results of
   typical simulations in practice.  Perhaps for most real-life
   simulations (e.g., when simulating a factory, or a restaurant, or a
   communication network), the results will not be affected, because
   the model will typically not be synchronized with the bad set of
   lags [...] (unless we are very unlucky).  But that could happen,
   and if it does, disaster will strike.  There are also classes of
   applications dealing specifically with random points in high
   dimensional space, and where those bad structures could have a
   dramatic effect.  Such applications arise, for example, in
   computational physics, or in statistics, when estimating
   complicated (perhaps multidimensional) distributions or
   expectations by simulation.