Random Number Generators

the algorithm as in Randomized Incremental Construction, or as part of a
model in a simulation as in Molecular Dynamics Simulations, or to generate
random inputs to test the algorithm.
(Pseudo-) Random number generators are, in most cases, deterministic algorithms
whose output is supposed to look like a random sequence. The only randomness
present is the seed (or starting point) provided by the user.

This mini course will present various types of random number generators and show
how to judge the quality of a random number generator. The course is mainly
directed at users of random number generators. Quasi random number
generators and random number generators for cryptographic purposes will not
be covered since these work very differently.

Topics covered:

Uniform Distribution
--------------------
With respect to random number generators, the uniform distribution is the
most important distribution, since almost all generators for other distributions
work by transforming uniform random numbers into random numbers with the
desired distribution. For this reason, most research is concerned with
the generation of uniform random numbers.
Some types of uniform random number generators:
Linear Congruential Generators (LCGs)
Lagged Fibonacci Generators
Shift Register Generators
Inversive Congruential Generators
...


Other Distributions
-------------------
Some general methods for the transformation of uniform random numbers
into random numbers of other distributions like inversion, the
acceptance--rejection method, ration of uniforms ... will be covered.
Also some methods for special distributions like the Box--Muller method
for the normal distribution will be presented.


Quality of random number generators
-----------------------------------
The random number generators considered here are deterministic algorithms
whose output is supposed to look like a random sequence of the proper
distribution. That means it should be ``hard'' to distinguish the
output from a random sequence. There are theoretical and practical
criteria for the quality of random number generators.
Theoretical criteria concern, in general, the whole period of the
generator and include things like period length, number of sub-cycles
or the discrepancy of the sequence.
Practical criteria are concerned with the behavior of the generators
in statistical tests like the runs test or the poker test.


Miscellaneous
-----------
Implementation issues
Usable length of the period
Random number generators and parallel algorithms
...


No prior knowledge of random number generators is assumed and the
mini course is intended to be self contained.