Java Reference
In-Depth Information
used to generate them and thus cannot possibly be random. Generally, it is
sufficient to produce
pseudorandom numbers,
or numbers that
appear
to be
random because they satisfy many of the properties of random numbers. Pro-
ducing them is much easier said than done.
Suppose that we need to simulate a coin flip. One way to do so is to exam-
ine the system clock. Presumably, the system clock maintains the number of
seconds as part of the current time. If this number is even, we can return 0 (for
heads); if it is odd, we can return 1 (for tails). The problem is that this strategy
does not work well if we need a sequence of random numbers. One second is
a long time, and the clock might not change at all while the program is run-
ning, generating all 0s or all 1s, which is hardly a random sequence. Even if
the time were recorded in units of microseconds (or smaller) and the program
were running by itself, the sequence of numbers generated would be far from
random because the time between calls to the generator would be essentially
identical on every program invocation.
Pseudorandom
numbers
have
many properties of
random numbers.
Good random num-
ber generators are
hard to find.
What we really need is a
sequence
of pseudorandom numbers, that is, a
sequence with the same properties as a random sequence. Suppose that we
want random numbers between 0 and 999, uniformly distributed. In a
uniform
distribution,
all numbers in the specified range are equally likely to occur.
Other distributions are also widely used. The class skeleton shown in
Figure 9.1 supports several distributions, and some of the basic methods are
identical to the
java.util.Random
class. Most distributions can be derived from
the uniform distribution, so that is the one we consider first. The following
properties hold if the sequence 0, ..., 999 is a true uniform distribution.
In a
uniform distri-
bution
, all numbers
in the specified
range are equally
likely to occur.
The first number is equally likely to be 0, 1, 2, ..., 999.
n
The
i
th number is equally likely to be 0, 1, 2, ..., 999.
n
n
The expected average of all the generated numbers is 499.5.
These properties are not particularly restrictive. For instance, we could
generate the first number by examining a system clock that was accurate to
1 ms and then using the number of milliseconds. We could generate subse-
quent numbers by adding 1 to the preceding number, and so on. Clearly, after
1,000 numbers are generated, all the previous properties hold. However,
stronger properties do not.
Two stronger properties that would hold for uniformly distributed random
numbers are the following.
Typically a random
sequence, rather
than one random
number, is required.
The sum of two consecutive random numbers is equally likely to be
even or odd.
n
If 1,000 numbers are randomly generated, some will be duplicated.
(Roughly 368 numbers will never appear.)
n
Search WWH ::
Custom Search