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.