Page 79 - DCAP601_SIMULATION_AND_MODELING

Unit 5: Discrete System Simulation (II)

Another common entropy source is the behavior of human users of the system, if such users Notes
exist. While humans are not considered good randomness generators upon request, they generate
random behavior quite well in the context of playing mixed strategy games. The utilization of
human game play entropy for randomness generation was studied by Ran Halprin and Moni
Naor, see “Games for Extracting Randomness”.

Computational Methods

Pseudo-random Number Generators (PRNGs) are algorithms that can automatically create long
runs (for example, millions of numbers long) with good random properties but eventually the
sequence repeats (or the memory usage grows without bound). One of the most common PRNG
is the linear congruential generator, w hich uses the recurrence X = (aX + b) mod m to generate
n+1 n
numbers. The maximum number of numbers the formula can produce is the modulus, m. To
avoid certain non-random properties of a single linear congruential generator, several such
random number generators with slightly different values of the multiplier confident and are
typically used in parallel, with a “master” random number generator that selects from among
the several different generators.
Most computer programming languages include functions or library routines that purport to be
random number generators. They are often designed to provide a random byte or word, or a
floating point number uniformly distributed between 0 and 1.
Such library functions often have poor statistical properties and some will repeat patterns after
only tens of thousands of trials. They are often initialized using a computer’s real time clock as
the seed. These functions may provide enough randomness for certain tasks (for example video
games) but are unsuitable where high-quality randomness is required, such as in cryptographic
applications, statistics or numerical analysis. Much higher quality random number sources are
available on most operating systems; for example /dev/random on various BSD flavors, Linux,
Mac OS X, IRIX, and Solaris, or CryptGenRandom for Microsoft Windows.

Notes A simple pen-and-paper method for generating random numbers is the so-called
middle square method suggested by John Von Neumann. While simple to implement, its
output is of poor quality.

Practical Applications and Uses of Random Numbers

Random number generators have applications in gambling, statistical sampling, computer
simulation, cryptography, and other areas where a random number is useful in producing an
unpredictable result.
Note that, in general, where unpredictability is paramount–such as in security applications–
hardware generators are generally preferred, where feasible, over pseudo-random algorithms.
Random number generators are very useful in developing Monte Carlo method simulations as
debugging is facilitated by the ability to run the same sequence of random numbers again by
starting from the same random seed. They are also used in cryptography so long as the seed is
secret. Sender and receiver can generate the same set of numbers automatically to use as keys.
The generation of pseudo-random numbers is an important and common task in computer
programming. While cryptography and certain numerical algorithms require a very high degree
of apparent randomness, many other operations only need a modest amount of unpredictability.
Some simple examples might be presenting a user with a “Random Quote of the Day”, or
determining which way a computer-controlled adversary might move in a computer game.
Weaker forms of randomness are also closely associated with hash algorithms and in creating
amortized searching and sorting algorithms.

LOVELY PROFESSIONAL UNIVERSITY 73