Summary of Francois Panneton's thesis
Keywords : Random number
generators, linear recurrence, Monte Carlo, quasi-Monte Carlo,
simulation, uniform point sets, equidistribution, polynomial lattice,
uniformity.
In this thesis, we are interested in the development of new random
number generators (RNG) that use a linear recurrence in a finite field
of characteristic 2. We also use these recurrences to define new point
sets for quasi-Monte Carlo applications.
We first define the criteria used to choose the parameters of our
generators. Among them, we find the equidistribution and the minimal
distance between two points from a point set. For this last
criterion, we developed a new algorithm that computes the minimal
distance in average time O(n) where n is the cardinality of the point
set.
We then define new RNGs that use a linear recurrence in F_{2^w}, the
finite field with 2^w elements. With these generators, we also
define new point sets for quasi-Monte Carlo applications. The
vast majority of the two-dimensional projections of these new point
sets have a perfect equidistribution.
Also, we define a new family of generators known as WELL RNGs.
The equidistribution of these generators is almost perfect and the
number of non zero coefficients in the characteristic polynomial is
close to k/2 where k is its degree. The speed of these generators is
comparable to other fast generators.
We conclude this thesis by analyzing a family of generators proposed by
Marsaglia [1] known as ``xorshift generators''. We analyze their
theoretical properties and look for the best generators. Even
though they have, in general, good equidistribution properties, the
recurrence they use is too simple to produce good generators. We
show this by testing many generators empirically.
[1] G. Marsaglia. Xorshift RNGs. Journal of Statistical Software, 8(14)
:1 6, 2003. See http://www.jstatsoft.org/v08/i14/xorshift.pdf.