Re: Software Accuracy : autocorrelation _is_ the problem

BRAD GILE ( (no email) )
Wed, 16 Jun 1999 13:04:03 -0500

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=3D8. For double precision, n=3D16. I bel=
ieve
even Mathematica cannot go beyond n=3D500. 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 continuou=
s
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=3D1, 2, 3,... .

So, if you are unlucky and have some cycles of length k (**)
in your simulations, then your simulations could be
completely wrong. If there is no such cycles the effect
is less clear. The chances of having a fixed cycle of length
k are near zero but having an average cycle of length k
is less improbable.

The technique of shuffling (see Numerical Recipes in C,
for example) can (or seems to) remove the autocorrelation
but the experts recommend not to use it since its
behavior is not well known.

The following URL is a good starting point to find
more information on RNGs on the web:

http://cgm.cs.mcgill.ca/~luc/rng.html

Below is a supposedly (according to L. Devroye) very
good...

/* uniform [0,1] random number generator
developed by Pierre Lecuyer based on a clever
and tested combination of two linear congruential
sequences
*/

/*
s1 and s2 are the seeds (nonnegative integers)
*/

#include <math.h>

double uni()
{
static long s1 =3D 55555;
static long s2 =3D 99999;
static double factor =3D 1.0/2147483563.0;
register long k,z;
k=3D s1 /53668;
s1 =3D40014*(s1%53668)-k*12211;
if (s1 < 0) s1 +=3D 2147483563;
k=3Ds2/52774;
s2=3D40692*(s2%52774)-k*3791;
if (s2 < 0) s2 +=3D 2147483399;

/*
z =3D abs(s1 ^ s2);
*/
z=3D (s1 - 2147483563) + s2;
if (z < 1) z +=3D 2147483562;

return(((double)(z))*factor);
}

Fran=E7ois Dufresne

(*) : bias will probably be a consequence of autocorrelation...

(**) : or k/2, k/4, 2k, etc...

---Ecole des HEC - U. of Lausanne - 1015 Lausanne - Switzerland



Visit the CAS Web Site at http://www.casact.org=FF=FF=FF=FF=FF=FF=FF=FF=FF=FF=FF=FF=FF=FF=FF=3DTo subscribe or unsubscri=be from CASNET:Send an e-mail to caslists@lists.casact.orgType in the body join casnet to subscribeor leave casnet to unsubscribe.----------





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