Transcript Lab for Remote Sensing Hydrology and Spatial

An Introduction to R
Pseudo Random Number Generation (PRNG)
Prof. Ke-Sheng Cheng
Dept. of Bioenvironmental Systems Eng.
National Taiwan University
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
1
Pseudo Random Number Generator
(PRNG)


Computer simulation of random variables is the
task of using computers to generate many random
numbers that are independent and identically
distributed. It is also known as random number
generation (RNG).
In fact, these computer-generated random numbers
form a deterministic sequence, and the same list of
numbers will be cycled over and over again. This
cycle can be made to be so long that the lack of
true independence is unimportant.
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
2


RSLAB-NTU
Therefore, such computer codes are often
termed pseudo-random number generators
(PRNG).
There exist mathematical transformation
methods to obtain other distributions from
uniform variates. For this reason, most PRNGs
found in software libraries produce uniform
random numbers in the unit interval (0, 1).
Lab for Remote Sensing Hydrology
and Spatial Modeling
3
Linear Congruential Generator

RSLAB-NTU
Generation of random samples of various
probability densities is based random
samples of the uniform density U[0,1).
Therefore, the algorithm of generating
random numbers of U[0,1) is essential. This
can be achieved by the Linear Congruential
Generator (LCG) described below.
Lab for Remote Sensing Hydrology
and Spatial Modeling
4

RSLAB-NTU
Let a sequence of numbers xn be defined by
xn  [axn 1  c] modulo m
where a, c, and m are given positive integers. The
above equation means that axn 1  c is divided by
m and the remainder is taken as the value of xn . The
quantity xn / m is then taken as an approximation to
the value of a U[0,1) random variable. When c = 0,
the algorithm is also called a pure multiplicative
generator.
Lab for Remote Sensing Hydrology
and Spatial Modeling
5


RSLAB-NTU
A guideline for selection of a and m (c =0) is that m
be chosen to be a large prime number that can be
fitted to the computer word size. For a 32-bit word
computer, m = 231  1 and a = 75 result in desired
properties.
For small computers without a random number
generator, the following a, c, and m are found to be
satisfactory when the LCG algorithm is used:
a  25173, c  13849 and m  65536.
Lab for Remote Sensing Hydrology
and Spatial Modeling
6
PROBABILITY INTEGRAL
TRANSFORMATION


RSLAB-NTU
The PIT method is based on the property that a
random variable X with CDF FX () can be
transformed into a random variable U with uniform
distribution over the interval (0,1) by defining
U  FX (X )
Conversely, if U is uniformly distributed over the
1
X

F
interval (0,1), then
X (U ) has cumulative
distribution function FX () .
Lab for Remote Sensing Hydrology
and Spatial Modeling
7
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
8
Demonstration of the Probability
Integration Transformation through
stochastic simulation
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
9
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
10
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
11
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
12
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
13


RSLAB-NTU
For random variables whose cumulative
distribution function cannot be expressed by
a close form the probability integral
transformation technique cannot be used for
generating random numbers of these random
variables.
The normal distribution is one such random
variable.
Lab for Remote Sensing Hydrology
and Spatial Modeling
14
The Acceptance/Rejection
Method

RSLAB-NTU
This method uses an auxiliary density for
generation of random quantities from another
distribution. This method is particularly useful
for generating random numbers of random
variables whose cumulative distribution
functions cannot be expressed in closed form.
Lab for Remote Sensing Hydrology
and Spatial Modeling
15


RSLAB-NTU
Suppose that we want to generate random
numbers of a random variable X with density
f(X).
An auxiliary density g(X) which we know
how to generate random samples is identified
and cg(X) is everywhere no less than f(X) for
some constant c, i.e.,
f ( x)  cg ( x) x
Lab for Remote Sensing Hydrology
and Spatial Modeling
16
cg(X)
f(X)
X
RSLAB-NTU
Lab for Remote Sensing Hydrology
and Spatial Modeling
17




RSLAB-NTU
Generate a random number x of density g(X),
Generate a random number u from the density
U[0,cg(x)),
Reject x if u > f(x); otherwise, x is accepted as a
random number form f(X),
Repeat the above steps until the desired number of
random numbers are obtained.
Lab for Remote Sensing Hydrology
and Spatial Modeling
18