Articles indicating that congruential sequences produce
points on a lattice and hence fall in parallel hyperplanes
were written in the 60's, when drafts were in longhand,
subsequently typed by skilled secretaries using type-balls
for mathematical symbols, Greek letters, subscripts, etc.
There were no
TeX? or postscript in those days, and thus no
readily converted-to-web versions. But old journal
articles may be available from sources such as JSTOR.
The theory behind the lattice structure and the
"falling in planes" can be summarized in this way:
Let x(1),x(2),x(3),x(4),... be a sequence of integers generated
by the recursion
x(n)=a*x(n-1)+b mod m.
Then (in 3-space) if (0,b,a*b+b) is subtracted from any point
(x(i),x(i+1),x(i+2)),
the resulting point (x(i),x(i+1)-b,x(i+2)-a*b-b) lies on the lattice
generated by the three points (1,a,a^2), (0,m,0), (0,0,m).
(For 4-space, subtract (0,b,a*b+b,a^2*b+a*b+b) from each point
(x(i),x(i+1),x(i+2),x(i+3)) to get the lattice generated by the four points
(1,a,a^2,a^3), (0,m,0,0), (0,0,m,0), (0,0,0,m), and so on.)
(A lattice in n-space is the set of all linear combinations of
n points when the coefficients of the linear combinations are
restricted to integers, i.e, (for 3-space) all points
r*alpha + s*beta + t*gamma
with r,s and t integers and alpha,beta,gamma three points in space.
Thus (0,0,0) is one of the points of the lattice. For congruential
sequences, the lattice may be offset from (0,0,0), and subtracting
(0,b,a*b+b) from each point makes the lattice proper, containing (0,0,0).)
The points in a lattice fall in parallel planes; good congruential RNG's
might have nearly "cubic" lattices so that the parallel hyperplanes
are nearly equally spaced no matter how defined, while not-so-good
RNG's might have widely spaced hyperplanes with large in-between
regions containing no points.
Proof for the general lattice structure readily follows from that for
3-space:
Let g(x) mean the integer part (floor function) of x/m, so that
x(n) = a*x(n-1)+b - m*g(a*x(n-1)+b)
The point (x(i),x(i+1),x(i+2)) can be expressed as
( r, a*r+b-m*g(a*r+b),
a^2*r+a*b-a*m*g(a*r+b)+b-m*g(a^2*r+a*b-a*m*g(a*r+b)) )
and subtracting the "centering vector" (0,b,a*b+b) from this yields
( r, a*r-m*g(a*r+b),
a^2*r-a*m*g(a*r+b)-m*g(a^2*r+a*b-a*m*g(a*r+b)) ),
that is,
r*(1,a,a^2) + s*(0,m,0) + t*(0,0,m)
for integers r,s,t.
The musical "My Fair Lady" was a hit in the 60's, and its
"The rain in Spain falls mainly in the plains" lyric
led to the suggestion by Wallace Givens that I use the title
"Random numbers fall mainly in the planes" for the
article in Proceedings National Academy Sciences, v61,25-28,1968.
I attempt a complete treatment,
"The structure of linear congruential sequences"
in the book
"Applications of Number Theory to Numerical Analysis",
S. K. Zaremba, editor, Academic Press, 1972
George Marsaglia
--
DaleBrayden - 01 Dec 2002
Books RSS
