Transcript Random Number Generators

Random Number
Generators
Random Number Generators
 Based
upon specific mathematical
algorithms
 Which are repeatable and sequential
Random
 Truly
Random
– Exhibiting true randomness
 Pseudorandom
– Appearance of randomness but having a
specific repeatable pattern
 Quasi-random
– Having a set of non-random numbers in
a randomized order
Problems
 Difficult
to isolate
– Often need to replace current generator
– Require
 Knowledge
of current generator
 Sometimes in-depth understanding of
random number generators themselves
 Large
scale tests cause most
problems
– Needing sometimes millions or billions
of random numbers
Desirable Properties
 When
performing Monte Carlo
Simulations
– Attributes of each particle should be
independent of those attributes of any
other particle
– Fill the entire attribute space in a
manner which is consistent with the
physics
Random Number Cycle
 Basis
– sequence of pseudorandom integers
 Some
 Integers
exceptions
(“Fixed”)
– Manipulated arithmetically to yield
floating point (“real”)
 Can
be presented in either Integer or
Real numbers
Cycle
What Does This Show Us?
 Properties
of pseudorandom
sequences of integers
– The sequence has a finite number of
integers
– The sequence gets traversed in a
particular order
– The sequence repeats if the period of
the generator is exceeded
LCG
 Most
commonly used RNG
– Linear Congruential Generator
 Requires
initial “seed” denoted as X0
 Appears random because of Modulo function
 Next “random” number depends heavily on
previous X
– Typical of linear, congruential generators
– Restricts period
Equations - LCG
Using LCG
Choosing Correct Input is Key
 LCG (a,c,m,X0)

– LCG (5, 1, 16, 1)
 Yields
–


1,6,15,12,13,2,11,8,9,14,7,4,5,10,3,0,
1,6,15,12,13,2,11,8,9,14,…
When the next result depends upon only the
previous integer, the longest period possible is P=M
 Odd/Even pattern
 lack of randomness results from using a power of two
for M

Cycle LCG(5,1,16,1)
Table
Example #2
 LCG(5,0,16,1)
– Yields - 1,5,9,13,1,5,9,13,…
– M is a power of 2 (here: 2^4)
 C=0
 Maximum
period is going to be 2^(m-2)
– Correlation (each differ by 4)
Cycle (5,0,16,1)
Seed
 Using
the date and time
– Enter the date and time into an
equations and return an integer then
make sure it is odd
– Standard seed for these equations
Overflow & Negative Numbers
 Using
large values of a and large
values of M are needed
– Often 31 bits long
 On
32 bit machines
– A*M results in 62 bit number
– Overflow
 Can
result in 32nd bit being a negative
N-Tuple Generalization
 Choose
R1 and R2
– Choose Rn and R(n+1)
– Then plot this point of interest in a
surrounding area.
 Plot
these points in succession
 The area will be uniformly covered by the
LCG in a “random” order
– Covering of only part of the unit or certain areas
of the unit would prove to be not useful for Monte
Carlo Methods
Embarrassingly Parallel'
 Little
or no interprocessor
communication
 Easy to code
N Streams
N
Streams
– N independent random numbers
– N independent processes
 Need
to find N seeds far away from
each other on the cycle
Find Seeds

Find Seeds
– LCG rule successively applied:
Lagged Fibonacci Generators

Increasingly popular
– Lags are k and l
– M is power of 2
 With
proper choice of k and L
 Period of Generator can be
– [(2^L)-1] * [2^(m-1)]
LFG
 Computationally
simple
– Integer add
– Logical AND
– Decrement of 2 array pointers
– Must keep L words current in memory
– LCG needs only one
LFG (cont)
LFG are an attempt to improve LCG
 Similar to Combined LCG

– Take 2 previous numbers in the sequence to
produce a new number
– Where p and q are the “lags”
– Some arithmetic computation is performed
– Then mod that answer for the next number
Monte Carlo Methods
Overview
 Introduction
 History
 Examples
 Applications
 Real
Life practices
Introduction
 Define
Monte Carlo Method
– The Monte Carlo method is a numerical
method for solving mathematical
problems using stochastic sampling.
– It performs simulation of any process
whose development is influenced by
random factors, but also if the given
problem involves no chance, the method
enables artificial construction of a
probabilistic model.
Introduction cont…

Similarly, Monte Carlo methods randomly
select values to create scenarios of a
problem. These values are taken from
within a fixed range and selected to fit a
probability distribution [e.g. bell curve,
linear distribution, etc.]. This is like rolling
a dice. The outcome is always within the
range of 1 to 6 and it follows a linear
distribution - there is an equal opportunity
for any number to be the outcome.
Introduction cont…
MC method is often referred to as the
“method of last resort”, as it is apt to
consume large computing resources;
 Characteristics:
– consuming vast computing resources
– have historically had to be executed
upon the fastest computers available at
the time
– and employ the most advanced
algorithms
– implemented with substantial
programming acumen.

Introduction cont…
 Major
components of Monte Carlo
methods:
– Probability distribution functions
– Random number generator
– Scoring
– Error estimation
– Variance reduction techniques
– Parallelization and vectorization
History

Where does Monte Carlo method come
from? When? Who?
– The name "Monte Carlo" comes from the city
of Monte Carlo in the principality of Monaco,
famous for its gambling house
– Birth date of the Monte Carlo method is 1949,
when an articale entitled "The Monte Carlo
Method"( by N. Metropolis and S. Ulam )
appeared.
– The American mathematicians J. Neyman and
S. Ulam are considered its originators.
History cont…
History cont…
The theoretical foundation of the method
had been known long before first articles
were published.
 Well before 1949 certain problems in
statistics were sometimes solved by
means of random sampling
 However, simulation of random variables
by hand is a laborious process
 Use of the Monte Carlo method as a
universal numerical technique became
practical only with the advent of
computers and high-quality
pseudorandom number generators

History cont…

Buffon's needle problem
– In 1768 Buffon, a French mathematician,
experimentally determined a value of π by
casting a needle on a ruled grid
Lord Rayleigh even delved into this field
near the turn of the century.
 Fredericks and Levy in 1928 showed how
the method could be used to solve
boundary value problems
 Enrico Fermi in the 1930's used Monte
Carlo in the calculation of neutron
diffusion (involving nuclear reactors )

History cont…
 In
the 1940's, a formal foundation
for the Monte Carlo method was
developed by von Neumann (PDE)
 Stanislaw Ulam realized the
importance of the digital computer in
the implementation of the approach
from collaboration results of the work
on the Manhattan project during
World War II
Examples
 Simple
Example to Understand:
computing the area of a plane figure
S.
– completely arbitary figure with a
curvilinear boundary, given graphically
or analytically, connected or consisting
of several pieces
– assume that it is contained completely
within the unit square.
Examples cont…
Figure S in the unit square, being covered with sampling points
randomly
Examples cont…
 Applying
Randomness to the
example:
– Choose at random N points in the
square and designate the number of
points lying inside S by N'. It is
geometrically obvious that the area of S
is approximately equal to the ratio N'/N.
The greater the N, the greater the
accuracy of this estimate.
Examples cont…
 Buffon's
Needle:
– A simple Monte Carlo method for the
estimation of the value of π, 3.1415926
– Assumptions:
 Suppose
you have a tabletop with a number
of parallel lines drawn on it, which are
equally spaced (say the spacing is 1 inch,
for example).
 Suppose you also have a pin or needle,
which is also an inch long.
Examples cont…

Dropping needles on the tablet:
– The needle crosses or touches one of the lines
– The needle crosses no lines
Keep dropping this needle over and over
on the table
 Record the statistics.

– Keep track of both the total number of times
that the needle is randomly dropped on the
table N, and the number of times that it
crosses a line N’.
Examples cont…
 Findings:
– 2N/N’=π
– Because, the probability on any given
drop of the needle that it should cross a
line is given by 2/pi
– After many tries, N/N’ will approach the
probability number.
Applications
 Monte
Carlo methods can help in
design and prediction of behavior of
systems in nuclear applications and
radiation physics
 The use of MC in the area of nuclear
power has undergone an important
evolution. Notable are the extensions
to compute burnup in reactor cores,
and full core neutronic simulations.
Applications cont…
 help
researchers understand the
probability of the occurrence of an
adverse effect associated with
exposures to chemicals. Monte Carlo
sampling simulates the distribution
of total exposures, by simulating
random samples of factors
associated with each exposure route
and accumulating them to arrive at
an individual total exposure.
Applications cont…

The use of MC methods to model physical
problems allows us to examine more
complex systems than we otherwise can.
Solving equations which describe the
interactions between two atoms is fairly
simple; solving the same equations for
hundreds or thousands of atoms is
impossible. With MC methods, a large
system can be sampled in a number of
random configurations, and that data can
be used to describe the system as a
whole.
Applications cont…
 Random
numbers generated by the
computer are used to simulate
naturally random processes
 many previously intractable
thermodynamic and quantum
mechanics problems have been
solved using Monte Carlo techniques
Real Life Practice
 Quantum
Monte Carlo
– The microscopic world is described by
quantum mechanics. We need to use
simulation techniques to “solve” manybody quantum problems.
– Both the wavefunction and expectation
values are determined by the
simulations.
– QMC gives most accurate method for
general quantum many-body systems.
Real Life Practice cont…
Weather
 Equipment Productivity
 Soil Conditions
•
Projects are often associated with a
high degree of uncertainty resulting
from the unpredictable nature of
events
Real Life Practice cont…

Risk Analysis and Risk Management
– Monte Carlo Simulation is a valuable modeling
tool that generates multiple scenarios
depending upon the data and the assumptions
fed into the model.
– Simulation calculates multiple scenarios by
repeatedly inserting different sampling values
from probability distribution for the uncertain
variables into the computerized spread-sheet.
– probability or percentage chance that a
particular forecast value will fall within a
certain specified range.
Why has the Monte Carlo method
become so popular?
 Analytic
methods tend to be
prohibitive (but some very difficult
problems have finally been solved
using MC)
 Monte Carlo is somewhat intuitive
(and several good books have now
been written on the subject)
 Computers continue to get faster
and cheaper
Reference
 http://random.mat.sbg.ac.at/links/m
onte.html
 http://www.ccs.uky.edu/csep/csep.ht
ml