Monte Carlo Method (1)
Monte Carlo Method (1)
What is a monte carlo simulation? Monte carlo simulation is a numerical method based on the extensive use of random numbers for solving different problems Remark Monte Carlo simulation can be used to study not only stochastic problems(e.g, diffusion) but also non stochastic ones(Monte Carlo integration)
What is a Monte Carlo simulation? Monte Carlo simulation is a numerical method based on the extensive use of random numbers for solving different problems. Remark: Monte Carlo simulation can be used to study not only stochastic problems (e.g., diffusion) but also non stochastic ones (Monte Carlo integration)
A short history Buffon's problem of needle throwing: A needle of length L is thrown at random onto a plane with straight parallel lines which are separated by a distance d(d>l) What is the probability p that the needle will intersect one of these li Ines Georges Louis Leclerc comte de buffon(1707-1788): Eminent French naturalist Solution P=2L/(d Reference: G. Comte de buffon, Essai darithmetique morale, Supplement a I Histoire naturelle. VoL 41777 Remark Laplace suggested that the method described in Buffon's problem can be used as a stochastic method to calculate the value of t
A short history Buffon’s problem of needle throwing: A needle of length L is thrown at random onto a plane with straight parallel lines which are separated by a distance d (d > L). What is the probability P that the needle will intersect one of these lines? Georges Louis Leclerc comte de Buffon (1707 - 1788): Eminent French naturalist. Solution: P = 2L/(pd) Reference: G. Comte de Buffon, Essai d ’arithmétique morale, Supplément à l ’Histoire Naturelle, Vol. 4, 1777. Remark: Laplace suggested that the method described in Buffon’s problem can be used as a stochastic method to calculate the value of p
Condition for intersection h=Lsin(0)/2>X Geometric implication ALSIna P=S/(d/2/2) S1=L2 d/2 L/2 兀/20
q h x d Condition for intersection: h=Lsin(q)/2 > x Geometric implication: P = SI /(d/2 p/2) SI = L/2 x d/2 L/2 p/2 q x=Lsin(q)/2 I
Anecdote In 1901, Lazzerini (ltalian mathematician) performed a simulation by spinning round and dropping a needle 3407 times. He estimated T to be 3. 1415929(accurate to the seventh number after the point!
Anecdote: In 1901, Lazzerini (Italian mathematician) performed a simulation by spinning round and dropping a needle 3407 times. He estimated p to be 3.1415929 (accurate to the seventh number after the point!)
Monte carlo integration XLSin(0)/2 S与m0 d/2 L/2 S can be calculated from Pd/4(Pis the probability of finding a random point in the area under the red curve) π/2 Exercise Write a program to calculate t by using the method of Buffon with d=l and L=3 /4
Exercise Write a program to calculate p by using the method of Buffon with d=1 and L=3/4. Monte Carlo integration x d/2 L/2 p/2 q x=Lsin(q)/2 I = /2 0 sin 2 p dq q L SI SI can be calculated from Pdp/4 (P is the probability of finding a random point in the area under the red curve)
Random number generation General remark All the random numbers generated on a computer are in fact pseudo random numbers which are produced through a deterministic algorithm Basic generator: It produces uniformly distributed random numbers on 0, 11 Desirable properties ofa random number generator It should generate sequences of random numbers which are uniform, uncorrelated with an extremely long period
Random number generation General remark: All the random numbers generated on a computer are in fact pseudorandom numbers which are produced through a deterministic algorithm! Basic generator: It produces uniformly distributed random numbers on [0,1]. Desirable properties of a random number generator: It should generate sequences of random numbers which are •uniform, •uncorrelated, •with an extremely long period
A widely used random-number generation method Congruential method. X=(axn +c)mod(m) Properties of this sequence X<m When a, c, Xo and m are integers, Eq (1)generates integers between 0 and m-1 Xn m gives pseudo-random numbers distributed on(0, 1) lllustration With a=3, c=l, m=16 and a seed Xo=2, we have the following sequences 2.7.6.3.10.15.14.11.2.7 The period of this sequence is 8
A widely used random-number generation method Congruential method: Xn = (aXn-1+c)mod(m) (1) Properties of this sequence: Xn < m When a, c, X0 and m are integers, Eq.(1) generates integers between 0 and m-1. Xn /m gives pseudo-random numbers distributed on (0,1). Illustration: With a=3, c=1, m=16 and a seed X0=2, we have the following sequences, 2, 7, 6, 3, 10, 15, 14, 11, 2, 7,… The period of this sequence is 8
Condition for a congruential generator to have a full period It can be shown that the congruential generator given in Eq (1)has a full period i e. m, if and only if )c and m have no common divisor (i. e, no common divisor other an 2)a=l mod(g) for every prime factor of m 3)a=l mod(4) if m is multiplier of 4 It is obvious that m should be as large as possible! m=231-1 is often used on a computer with 32 bits
Condition for a congruential generator to have a full period: It can be shown that the congruential generator given in Eq.(1) has a full period, i.e. m, if and only if 1) c and m have no common divisor (i.e., no common divisor other than 1); 2) a1 mod(g) for every prime factor of m; 3) a1 mod(4) if m is multiplier of 4. It is obvious that m should be as large as possible! m=231 -1 is often used on a computer with 32 bits
Statistical test of random number generators Uniformity test: Break up the interval between 0 and 1 into a large number of small bins and after generate a large number of random numbers check for uniformity in the numbers of entries in each bins(uniform histogram Parking lot test: Plot points in an m-dimensional space where the m-coordinates of each point are determined by m-successive calls to the random number generator. Then, look for regular structure (resulting from some correlation) Illustration good generator(parking lot test) bad generator(parking lot test) 0
Statistical test of random number generators Uniformity test: Break up the interval between 0 and 1 into a large number of small bins and after generate a large number of random numbers check for uniformity in the numbers of entries in each bins (uniform histogram). Parking lot test: Plot points in an m-dimensional space where the m-coordinates of each point are determined by m-successive calls to the random number generator. Then, look for regular structure (resulting from some correlation). Illustration: good generator (parking lot test) bad generator(parking lot test) 1 1 0 0 1 1 0 0