Transcript Monte Carlo Simulations

Monte Carlo Simulations
Steven Gollmer
Cedarville University
Meet and Greet Game
• Are there people here who share the same
birthday?
– Most births occur in September & October
– October 5th is the most common birthday
– May 22nd is the least common birthday
• What does this have to do with Monte Carlo?
– What is the probability that at least one pair of
people share a birthday in this room?
Birthday Attack
• Hash functions convert
arbitrary length data into a
fixed length string of data.
• Passwords can be hashed
for quicker verification.
• Documents can be hashed
and assigned to a digital
signature.
• Collisions occur when
documents hash to the
same value.
What impact does hashing have on security?
Cracking a password with a 64 bit hash with 100,000 attempts/second could
take 5.8 Myr, but a collision with the hacker’s guess will likely occur in 14 hr.
Probability
• Terms
– Event (A) – The outcome of an experiment.
– Sample space (W) – All possible outcomes for an
experiment.
A
– Probability – Ratio of |A| to |W | P ( A )  W
• What is the probability of rolling a seven on
two dice?
Probability of Rolling 7
Probability
0.2
0.15
2
0.1
3
0.05
0
2
4
6
8
Sum of Dice
P (7 ) 
10
12
4
6
36
• Chances are
1 out of 6
5
6
7
8
9
10
11 12
Birthday Problem
• What is the probability of shared birthdays if
there are N people in the room?
– N = 1, P(1) = 0%
– N = 365, P(365) = 100%
– N = 3,
P (3) 
365  364  3
365
In General
 365

 k

P(N ) 
365


k!

N
3

ni
ni !
365
1
364
A
A
B
A
B
A
B
A
A
 0 . 82 %
Combinations
N!
i!
Choices
Additional Complications
• What about 2 pairs of shared birthdays?
• What about triple shared birthdays?
• Are birthdays evenly distributed throughout
the year?
Monte Carlo Simulation
• Run multiple experiments, N0
– Individual outcomes are either 0 or 1 (Failure or
Success)
– Total number of successes, Ns
• Running more experiments give more
accurate results.
Probability
p 
N
s
N0
Relative error
Es 
1 p
N
s
Calculate the value of p
Find the % of points falling within a circle of radius 1.
N0 = 10,000
• p = 0.78140
• p = 3.1256 ± 0.0331
N0 = 100,000
2
Ap r
• p = 0.78522
• p = 3.1409 ± 0.0104
Monte Carlo – Birthday Problem
• 30 people in a room
• Count when collisions occur
• Probability theory – p = 0.7063
Non-Uniform Birthday Problem
• Theory – 70.63%
• Monte Carlo
– N=1k, p=70.4 ± 2.9%
– N=10k, p=71.39 ± 0.90%
– N=100k, p=70.90 ± 0.29%
– N=1M, p=70.95 ± 0.09%
• Normal Distribution
– 95% confidence interval
– 2s
Hypothesis Testing
• Hypothesis: Does a non-uniform birthday distribution give a
significantly different probability to the birthday problem?
• Test: Ran 2 Monte Carlo simulations using a uniform and nonuniform birthday distribution.
• Conclusion:
With a confidence level
better than 95%, the
hypothesis is verified. If a
higher confidence is desired,
use more experiments.
How well do climate models handle
transport of sunlight?
• Models assume that where clouds exist, they
have uniform optical properties.
• Marine Stratocumulus
• Off coast of S. California
• Representative of
uniform clouds.
• How do you test if this
assumption is valid?
Fractal Clouds and Monte Carlo
• Water content is
redistributed using a
fractal algorithm.
• Send photons through
the non-uniform cloud.
– 4096 bands
– 4 M photons
• Albedo – % reflected
– 15% difference at 60%
albedo
– <1% smoothing from
horizontal transport.
Other Applications
• Radiation Therapy
– Dosage from multiple
photon scattering in
tissue.
• Telescope design
– Impact of different
configurations.
• NOAA POES MEPED
– Measure particle radiation
that can disrupt
communications.
Conclusion – Monte Carlo Simulations
• Advantages
– Bypass the complexity of solving problems by
analytical methods ( trigonometry, calculus, D.E., etc.)
– Give solutions to problems too costly to compute
using standard numerical methods.
– Easily distributed to multiple processors or GPU’s
• Disadvantages
– Solution is statistical by nature.
– High precision comes at a high computational cost.
– Best used for problems with limited observables.
Credits
• www.r-project.org – R statistics program
• NASA & NOAA – Image source
• Wikipedia – General information and public
commons images.
• Cahalan et al. 1994. Independent Pixel and
Monte Carlo Estimates of Stratocumulus
Albedo. J. Atmos. Sci. 51:3776-90.
• http://www.dartmouth.edu/~chance/teaching
_aids/data/birthday.txt (1978 birthday data)