Hit-or-Miss Method Evaluation of a definite integral Lp(rb h h≥p(x) for anyx × Probability that a random point reside inside the area b M (6-ah N o N: Total number of points ≈(b-ahM·M: points that reside inside the region
Hit-or-Miss Method •Evaluation of a definite integral I x dx b a = ( ) h (x) for any x a b h X X X X X X O O O O O O •Probability that a random point O reside inside the area N M b a h I p − = ( ) N M I (b − a)h N : Total number of points M : points that reside inside the region
Hit-or-Miss Method Sample uniformly from the rectangular region la, b]x[o, hI The probability that we are below the curve is p h( -a So, if we can estimate p, we can estimate I I=ph(b-a) where p is our estimate of p
Hit-or-Miss Method Sample uniformly from the rectangular region [a,b]x[0,h] h(b - a) I p:= The probability that we are below the curve is So, if we can estimate p, we can estimate I: I p ˆh(b - a) ˆ = where is our estimate of p p ˆ
Hit-or-Miss Method We can easily estimate p ☆ throw n" uniform darts” at the rectangle %o let m be the number of times you end up under the curve y=g(x) M ☆let p N
Hit-or-Miss Method We can easily estimate p: ❖ throw N “uniform darts” at the rectangle N M ❖ let p ˆ = ❖ let M be the number of times you end up under the curve y=g(x)
Hit-or-Miss Method Start Set N: large integer M=0 Loop Choose a point x in a, b x=(b-a)1+a n times Choosea point y in [o h] y=hu2 if [x,y] reside inside then M=M+l /=(b-a)h(MN End
Hit-or-Miss Method a b h X X X X X X O O O O O O O Start Set N : large integer M = 0 Choose a point x in [a,b] Choose a point y in [0,h] if [x,y] reside inside then M = M+1 I = (b-a) h (M/N) End Loop N times x = (b−a)u1 + a hu2 y =
Hit-or-Miss Method rError Analysis of the Hit-or-Miss Method o It is important to know how accurate the result of simulations are o note that M is binomial(M, p) E(M=Np O(M=Np( E(D=E[ph(b-a]Em h(b-a0(=0h(b-al=o/M h(b-a) h(b-wE(=h(b-ap=l h2(b-a)2 h2(b-a)2p(1-p 2(M)= N o(=h(b-a (1-p h(b-a) M N
Hit-or-Miss Method Error Analysis of the Hit-or-Miss Method It is important to know how accurate the result of simulations are note that M is binomial(M,p) ( ) ( ) (1 ) 2 E M = Np M = Np − P E M h b a p I N h b a h b a N M E I E ph b a E = − = − = = − = − ( ) ( ) ( ) ) ˆ ( ) ( ) ˆ ( N h b a p p M N h b a h b a N M I ph b a ( ) (1 ) ( ) ( ) ) ˆ ( ) ( ) ˆ ( 2 2 2 2 2 2 2 2 2 − − = − = = − = − N M p p ˆ = (1 ) ( ) ) ˆ ( N M M N h b a I − − = 2 (1 ) 1 ) ( ) ˆ ( − − = − N N p p I h b a