Mail Archives: djgpp-workers/1998/12/10/06:07:13
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.
- Raw text -