Re: Software Accuracy : autocorrelation _is_ the problem

Francois Dufresne ( Francois.Dufresne@hec.unil.ch )
Wed, 16 Jun 1999 23:58:04 +0200

Note that the number "k" that I was referring to is _not_ the cycle of
the uniform RNG. These days, the cycle of most (good) uniform RNGs
is 2^32 or 2^31 (assuming that doing simulations using Maple V or
Mathematica is not an option -- i.e., too slow --). This number "k" can
be a "small" number, much smaller than the cycle of the URNG. This
autocorrelation is discussed in books on URNGs but generally not in
books on simulations in general.

F. Dufresne

At 13:04 16.06.99 -0500, you wrote:
There is a theoretical problem with ALL "random number generators" on a
finite interval, which arises from the way a computer represents real
numbers - n decimal places or less (and, of course, from a (albeit large)
finite interval. For single precision (which Excel's RAND and Visual
Basic's Rnd (which RAND uses), n=8. For double precision, n=16. I believe
even Mathematica cannot go beyond n=500. Whatever n may be, this means that
if I generate a "random" sample of size 10^n +1 from (0,1), for example, I
am guaranteed to have at least 1 duplication in the sample. If, however, I
take a "true" finite random sample (of whatever size!) from any continuous
distribution on (0,1), uniform or otherwise, the probability that a
duplication will occur in the sample is zero! This is one of those areas in
which probability theory begins to merge with philosophy.

Brad Gile

----------
From: Francois Dufresne <Francois.Dufresne@hec.unil.ch>
To: casnet@lists.casact.org
Subject: Software Accuracy : autocorrelation _is_ the problem
Date: Tuesday, June 15, 1999 5:45 PM

Generally, the problem with uniform random generators is
not the "bias" (*) but the autocorrelation:

if U1, U2, U3, ... are uniform random variates coming
from (especially) a linear congruential generator, then
there exists an integer k such that Ui and Ui+k are
_strongly_ correlated (near 1) for all i=1, 2, 3,... .

Francois Dufresne mailto://fdufresn@hec.unil.ch
Ecole des HEC
University of Lausanne tel.: +41.21/692.33.74
1015 Lausanne, Switzerland fax: +41.21/692.33.05

Visit the CAS Web Site at http://www.casact.org
===============================================
To subscribe or unsubscribe from CASNET:
Send an e-mail to caslists@lists.casact.org
Type in the body join casnet to subscribe
or leave casnet to unsubscribe.