Full HTML for

Scripted foilset CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration

Given by Geoffrey C. Fox at Delivered Lectures of CPS615 Basic Simulation Track for Computational Science on 22 October 96. Foils prepared 12 November 1996
Outside Index Summary of Material

This starts by finishing the simple overview of statistics
Covering Gaussian Random Numbers, Numerical Generation of Random Numbers both sequentially and in parallel
Then we describe the central limit theorem which underlies Monte Carlo method
Then it returns to Numerical Integration with the first part of discussion of Monte Carlo Integration

Table of Contents for full HTML of CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration

 Denote Foils where Image Critical
Denote Foils where HTML is sufficient
Denote Foils where Image is not available
Indicates Available audio which is lightpurpleed out if missing
1 Delivered Lectures for CPS615 -- Base Course for the Simulation Track of Computational Science
Fall Semester 1996 --
Lecture of October 22 - 1996
2 Abstract of Oct 22 1996 CPS615 Lecture
3 Generation of Gaussian Distributions
4 How do computers get random numbers?
5 Simple Random Number Generator
6 More on Generation of Random Numbers Numerically
7 An Illustration of Dangers of Correlations!
8 Parallel Random Numbers
9 The Law of Large Numbers or the Central Limit Theorem.
10 Shapes of Probability Distributions in Central Limit Theorem
11 Central Limit Theorem for Functions
12 Error in Central Limit Averaging
13 Simpson and Trapezoidal Rule Integrations
14 Newton-Cotes and Iterated Rules
15 Gaussian and Monte Carlo Integration
16 33:Why Monte Carlo Methods Are Best in Multidimensional Integrals
17 34:Best Multidimensional Integration Formulae
18 35:Distribution of Points in Two-dimensional Integral Done by Newton-Cotes Style Formulae
19 36:Distribution of Points in Two-dimensional Integral Done by Monte Carlo
20 37:Use of Bounding Boxes to Calculate --- I
21 38:Use of Bounding Boxes to Calculate --- II
22 39:Use of Bounding Boxes in Complicated Geometries --- I
23 40:Use of Bounding Boxes in Complicated Geometries --- II
24 41:IMPORTANCE Sampling Basic Theory
25 42:Choice of Importance Sampling Weight Function --- I
26 43:Choice of Importance Sampling Weight Function --- II
27 44:Monte Carlo Approach to Discrete Integrals
28 45:Why Use Monte Carlo for Summations?
29 46:Example of using Monte Carlo for Summations
30 47:The Wrong Way to Perform Multiple Monte Carlo
31 48:Stock Market Example of Multiple Monte Carlos --- I

Outside Index Summary of Material

HTML version of Scripted Foils prepared 12 November 1996

Foil 1 Delivered Lectures for CPS615 -- Base Course for the Simulation Track of Computational Science
Fall Semester 1996 --
Lecture of October 22 - 1996

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index
Geoffrey Fox
NPAC
Room 3-131 CST
111 College Place
Syracuse NY 13244-4100
HTML version of Scripted Foils prepared 12 November 1996

Foil 2 Abstract of Oct 22 1996 CPS615 Lecture

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index
This starts by finishing the simple overview of statistics
Covering Gaussian Random Numbers, Numerical Generation of Random Numbers both sequentially and in parallel
Then we describe the central limit theorem which underlies Monte Carlo method
Then it returns to Numerical Integration with the first part of discussion of Monte Carlo Integration
HTML version of Scripted Foils prepared 12 November 1996

Foil 3 Generation of Gaussian Distributions

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 83.5
"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 Scripted Foils prepared 12 November 1996

Foil 4 How do computers get random numbers?

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 132.4
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 Scripted Foils prepared 12 November 1996

Foil 5 Simple Random Number Generator

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 175.6
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 Scripted Foils prepared 12 November 1996

Foil 6 More on Generation of Random Numbers Numerically

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 319.6
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 Scripted Foils prepared 12 November 1996

Foil 7 An Illustration of Dangers of Correlations!

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 178.5
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 Scripted Foils prepared 12 November 1996

Foil 8 Parallel Random Numbers

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 325.4
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 Scripted Foils prepared 12 November 1996

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

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 220.3
Let xi be independent random numbers -- each with same distribution p(x).
HTML version of Scripted Foils prepared 12 November 1996

Foil 10 Shapes of Probability Distributions in Central Limit Theorem

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 129.6
Distribution of x: p(x) anything (reasonable)
Distribution of y: Gaussian but more importantly sharply peaked with width of peak -> 0
HTML version of Scripted Foils prepared 12 November 1996

Foil 11 Central Limit Theorem for Functions

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 97.9
HTML version of Scripted Foils prepared 12 November 1996

Foil 12 Error in Central Limit Averaging

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 214.5
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 Scripted Foils prepared 12 November 1996

Foil 13 Simpson and Trapezoidal Rule Integrations

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 67.6
We review the different Integration Formulae
HTML version of Scripted Foils prepared 12 November 1996

Foil 14 Newton-Cotes and Iterated Rules

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 76.3
HTML version of Scripted Foils prepared 12 November 1996

Foil 15 Gaussian and Monte Carlo Integration

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 73.4
Gaussian Integration
Unequally spaced prescribed points
Monte Carlo Integration
HTML version of Scripted Foils prepared 12 November 1996

Foil 16 33:Why Monte Carlo Methods Are Best in Multidimensional Integrals

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 198.7
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 17 34:Best Multidimensional Integration Formulae

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 72
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 18 35:Distribution of Points in Two-dimensional Integral Done by Newton-Cotes Style Formulae

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 25.9
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 19 36:Distribution of Points in Two-dimensional Integral Done by Monte Carlo

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 63.3
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 20 37:Use of Bounding Boxes to Calculate --- I

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 203
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 21 38:Use of Bounding Boxes to Calculate --- II

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 175.6
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 22 39:Use of Bounding Boxes in Complicated Geometries --- I

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 167
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 23 40:Use of Bounding Boxes in Complicated Geometries --- II

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 97.9
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 24 41:IMPORTANCE Sampling Basic Theory

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 276.4
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 25 42:Choice of Importance Sampling Weight Function --- I

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 70.5
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 26 43:Choice of Importance Sampling Weight Function --- II

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 156.9
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 27 44:Monte Carlo Approach to Discrete Integrals

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 417.6
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 28 45:Why Use Monte Carlo for Summations?

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 73.4
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 29 46:Example of using Monte Carlo for Summations

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 25.9
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 30 47:The Wrong Way to Perform Multiple Monte Carlo

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 96.4
See Original Foil
HTML version of Scripted Foils prepared 12 November 1996

Foil 31 48:Stock Market Example of Multiple Monte Carlos --- I

From CPS615-End of Basic Overview of Random Numbers and First Part of Monte Carlo Integration Delivered Lectures of CPS615 Basic Simulation Track for Computational Science -- 22 October 96. *
Full HTML Index Secs 331.2
See Original Foil
© 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 Fri Aug 15 1997