INTRODUCTION 3
Each sample is generated in response to the user’s request, so the samples are
unique.
Physical processes on the user’s computer can also be used to generate
random data. There are many ways to do this. For example, Davis, Ihaka,
and Fenstermacher (1994) describe a method of using randomness in the air
turbulence of disk drives. Toshiba produces a commercial product, Random
Master, that uses thermal noise in a semiconductor to generate uniform random
sequences. Random Master is packaged as a PCI board compatible with a range
of computer architectures from personal computers to supercomputers.
There are many issues to consider in developing “truly random” generators.
Our interest in this chapter will be in deterministic generators that can be
implemented in ordinary computer programs. The output of such generators is
pseudorandom.
Multiple Recursion
The most useful type of generator of pseudorandom processes updates a cur-
rent sequence of numbers in a manner that appears to be random. Such a
deterministic generator, f , yields numbers recursively, in a fixed sequence. The
previous k numbers (often just the single previous number) determine(s) the
next number:
x
i
= f(x
i−1
, ···,x
i−k
). (1.1)
The number of previous numbers used, k, is called the “order” of the generator.
Because the set of numbers directly representable in the computer is finite, the
sequence will repeat.
The set of values at the start of the recursion is called the seed. Each time
the recursion is begun with the same seed, the same sequence is generated.
The length of the sequence prior to beginning to repeat is called the period
or cycle length. (Sometimes, it is necessary to be more precise in defining the
period to account for the facts that, with some generators, different starting
subsequences will yield different periods and that the repetition may begin
without returning to the initial state.)
Predictability
Random number generation has applications in cryptography, where the re-
quirements for “randomness” are generally much more stringent than for or-
dinary applications in simulation. In cryptography, the objective is somewhat
different, leading to a dynamic concept of randomness that is essentially one
of predictability: a process is “random” if the known conditional probability of
the next event, given the previous history (or any other information, for that
matter), is no different from the known unconditional probability. (The condi-
tion of being “known” in such a definition is a primitive—undefined—concept.)
This kind of definition leads to the concept of a “one-way function” (see Luby,
1996). A one-way function is a function f such that, for any x in its domain,
剩余385页未读，继续阅读
