Full HTML for

Basic foilset CPS615 Foils -- set D: Statistics and Random Numbers (In preparation for Monte Carlo)

Given by Geoffrey C. Fox at CPS615 Basic Simulation Track for Computational Science on Fall Semester 95. Foils prepared 21 October 1995
Outside Index Summary of Material

This CPS615 Module has an overview of Random Numbers and statistics at the level needed for clear discussion of Monte Carlo Integration
It starts with basic properties of Random Numbers and extensions to multiple random variables and concept of independencs
Derivation of non-uniform probability distribution is illustrated with Gaussian distribution
We discuss computer generation of random variables for both sequential and parallel machines

Table of Contents for full HTML of CPS615 Foils -- set D: Statistics and Random Numbers (In preparation for Monte Carlo)

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
1 Lecture Stream 4
CPS 615 -- Computational Science in
Simulation Track
Statistics and Random Numbers
October 15, 1995
2 Abstract for Statistics and Random Numbers CPS615 Module
3 Basic Properties of Random Numbers
4 Means and Standard Deviations
5 Multiple Random Variables -- Correlation and Independence
6 Generation of Random Numbers
7 Derivation of NonUniform Probability Distributions
8 Mean and Standard Deviation of a function of a Random Variable
9 The Gaussian Distribution
10 Generation of Gaussian Distributions
11 How do computers get random numbers?
12 Simple Random Number Generator
13 More on Generation of Random Numbers Numerically
14 An Illustration of Dangers of Correlations!
15 Parallel Random Numbers
16 The Law of Large Numbers or the Central Limit Theorem.
17 Shapes of Probability Distributions in Central Limit Theorem
18 Central Limit Theorem for Functions
19 Error in Central Limit Averaging
20 Simpson and Trapezoidal Rule Integrations
21 Newton-Cotes and Iterated Rules
22 Gaussian and Monte Carlo Integration

Outside Index Summary of Material

HTML version of Basic Foils prepared 21 October 1995

Foil 1 Lecture Stream 4
CPS 615 -- Computational Science in
Simulation Track
Statistics and Random Numbers
October 15, 1995

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Geoffrey Fox
NPAC
Syracuse University
111 College Place
Syracuse NY 13244-4100
HTML version of Basic Foils prepared 21 October 1995

Foil 2 Abstract for Statistics and Random Numbers CPS615 Module

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
This CPS615 Module has an overview of Random Numbers and statistics at the level needed for clear discussion of Monte Carlo Integration
It starts with basic properties of Random Numbers and extensions to multiple random variables and concept of independencs
Derivation of non-uniform probability distribution is illustrated with Gaussian distribution
We discuss computer generation of random variables for both sequential and parallel machines
HTML version of Basic Foils prepared 21 October 1995

Foil 3 Basic Properties of Random Numbers

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Basic Foils prepared 21 October 1995

Foil 4 Means and Standard Deviations

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Basic Foils prepared 21 October 1995

Foil 5 Multiple Random Variables -- Correlation and Independence

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Basic Foils prepared 21 October 1995

Foil 6 Generation of Random Numbers

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Everything can be derived from uniform random numbers in the range [0,1] = [r1, r2]
Such random numbers are supplied by all serious scientific computers
HTML version of Basic Foils prepared 21 October 1995

Foil 7 Derivation of NonUniform Probability Distributions

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
You can derive other distributions by variations of the following dodge which uses functions of a uniform or other known random distribution
HTML version of Basic Foils prepared 21 October 1995

Foil 8 Mean and Standard Deviation of a function of a Random Variable

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Remember mean of x is
HTML version of Basic Foils prepared 21 October 1995

Foil 9 The Gaussian Distribution

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
m is the mean, s is standard deviation
HTML version of Basic Foils prepared 21 October 1995

Foil 10 Generation of Gaussian Distributions

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
"A Small Miracle" asserts that:
If x1 x2 are uniformly distributed in [0,1] -- Then:
  • g1 = (-2lnx1)1/2 cos 2px2
  • g2 = (-2lnx1)1/2 sin 2px2
are Gaussianly distributed
with mean = 0 and standard deviation = 1
while g1 and g2 are independent.
Proof: Consider
Integral:
with g1 g2 going to Polar coordinates (r=radius, angle)
and then transform to x1and x2 by
(-2lnx1)1/2 = radius i.e. x1=exp(-r2/2) and
2px2 = angle
HTML version of Basic Foils prepared 21 October 1995

Foil 11 How do computers get random numbers?

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Intuitively, random numbers come from large physical systems whose size implies that different atoms act (decay) independently, e.g. observed time of decay of radioactive particle is a random number.
Computers generate "pseudo random numbers"
  • For instance, with the sequence
xn+1 = (axn + c) mod m
  • where certain choices of a, c, m are good.
See Knuth1 or Numerical Recipes2.
1) Knuth, D.E., "Seminumerical Algorithms "Vol. 2, The Art of Computer Programming, Addison-Wesley Publishing Co.1969
2) Flannery,B.P., Press,W.H., Teukolsky,S.A., Vetterling,W.T., "Numerical Recipes in Fortran", The Art of Scientific Computing, Cambridge University Press 1992
HTML version of Basic Foils prepared 21 October 1995

Foil 12 Simple Random Number Generator

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Take the choice:
m = 231
a = 1103515245
c = 12345
Implemented in C as (64 bit)
newran = [a*oldran+c] & MASK
floatran = newran/2147483648.0
oldran = newran
floatran is uniformly distributed in [0,1]
MASK has lower 31 bits = 1and all higher bits = 0
This intuitively says that lower order bits of a complex multiplication are "essentially" random
HTML version of Basic Foils prepared 21 October 1995

Foil 13 More on Generation of Random Numbers Numerically

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
You do not need to "understand" this.
It is useful to check random number generator.
Is xn+i independent of xn for different values of i= 1...?
Also, note one must specify a "seed" = initial value x0
Then "random numbers" follow deterministically.
x0 => x1 => x2 ......
Set seed (x0) from "Time of Day"
Save seed so can rerun program..
HTML version of Basic Foils prepared 21 October 1995

Foil 14 An Illustration of Dangers of Correlations!

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
An old Turbo Pascal Random Number Generator
There are correlations ....
More than 1,000,000 random numbers generated by Turbo-Pascal v3.0 and plotted as (xn,xn+1) pairs.
HTML version of Basic Foils prepared 21 October 1995

Foil 15 Parallel Random Numbers

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Parallel random numbers are somewhat nontrivial.
If have N processors, must have numbers independent within and between processors.
See "Solving Problems on Concurrent Processors"
  • Fox, G.C., Johnson, M.A., Lyzenga, G.A., Otto, S.W., Salmon, J.K., Walker, D.W., "Solving Problems on Concurrent Processors", Vol. 1, Prentice-Hall, Inc. 1988; Vol. 2 1990.
One strategy is to have one stream and make every N'th number go to a given processor. This can be done very efficiently as described in reference above.
The result is:
  • Processor 0 x0 xN...
  • Processor 1 x1 xN+1.. .
    • .
    • .
  • Processor N-1 xN-1 x2N-1...
HTML version of Basic Foils prepared 21 October 1995

Foil 16 The Law of Large Numbers or the Central Limit Theorem.

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Let xi be independent random numbers -- each with same distribution p(x).
HTML version of Basic Foils prepared 21 October 1995

Foil 17 Shapes of Probability Distributions in Central Limit Theorem

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Distribution of x: p(x) anything (reasonable)
Distribution of y: Gaussian but more importantly sharply peaked with width of peak -> 0
HTML version of Basic Foils prepared 21 October 1995

Foil 18 Central Limit Theorem for Functions

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Basic Foils prepared 21 October 1995

Foil 19 Error in Central Limit Averaging

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
x and z are random variables with distributions - one has n copies of each
y = S (zi=f(xi))/n is a random variable with a distribution ,even though we only have one value for y we can calculate properties of this distribution including most importantly the expected error in y
This is most importantly applied in case f(x)=x and the above allows one to calculate error in basic central limit theorem application to y = S xii/n
HTML version of Basic Foils prepared 21 October 1995

Foil 20 Simpson and Trapezoidal Rule Integrations

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
We review the different Integration Formulae
HTML version of Basic Foils prepared 21 October 1995

Foil 21 Newton-Cotes and Iterated Rules

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
HTML version of Basic Foils prepared 21 October 1995

Foil 22 Gaussian and Monte Carlo Integration

From CPS615 Foils -- set D:Statistics and Random Numbers CPS615 Basic Simulation Track for Computational Science -- Fall Semester 95. *
Full HTML Index
Gaussian Integration
Unequally spaced prescribed points
Monte Carlo Integration
© Northeast Parallel Architectures Center, Syracuse University, npac@npac.syr.edu

If you have any comments about this server, send e-mail to webmaster@npac.syr.edu.

Page produced by wwwfoil on Wed May 13 1998