Popular in Course
Popular in Operations And Info Mgmt
This 3 page Class Notes was uploaded by Joshua Monahan I on Wednesday September 23, 2015. The Class Notes belongs to OPR991 at Drexel University taught by Staff in Fall. Since its upload, it has received 21 views. For similar materials see /class/212577/opr991-drexel-university in Operations And Info Mgmt at Drexel University.
Reviews for SimulationTheoryandApps
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/23/15
SIMULATION OF RARE EVENTS Using Importance Sampling Consider the probability of 45 or more heads in 50 tosses of a fair coin call it y On average one expects 25 heads and 45 is a far from average value In this case the probability under consideration is given in a closed form X Binomial5005 y E PX z 45 1 F45 gt lpbinom44 50 5 1 2104926e O9 To demonstrate Importance Sampling IS we estimate 7 using simulation First verify that it refers to a rare event Raw simulation is problematic in this setting We expect one occurrence of this event in half a billion trials Estimation using raw simulation would require a sample size that is a couple orders of magnitude higher in order to obtain a reasonably tight con dence interval Note that the Z X E 1X Z 45 is a Bernoulli yrandom variable where l is the indicator function of the event in brackets Its variance is 039 yl y Raw simulation generates a sample of n iid X1 and estimates 7 as zi zgg with a y17quot To get a 2 standard deviation confidence interval with size about 5 of y we need a sample size as follows 2 05yZ4 MM 12m i 739lm310 n n 05 Consider IS in this setting We change probability measure to one that accentuates X values equal or over 45 trying to generate an estimator with reduced variance We use Y N Binomial5009 where EY 45 The following identity is fundamental in IS EX ZX EY ZY Mm y HMO Where pX Y is the pmf under the original probability measure and pY Y is the pmf under the new measure The ratio of these two pmf s is called the likelihood ratio Y 5071 05 05 V 5w LYpXY Y pm 50 y 09 01 09 01 KY IS generates a sample of m iid Y according to the new measure estimates 7 as x A l m 7 ZZYLY mxa Using sample size m10000 only we obtain gt rndrbinom1000O500 gt 1ratio functionn45p105p209N50 ifp1p2g1p11p2fAngANn gt meanrndgt451ratiornd 1 2165614e O9 Compare to gt gamma1pbinom44505 gt gamma 1 2104926e O9 The IS standard error is gt sqrtvarrndgt451ratiornd1engthrnd 1 3918075e11 As opposed to raw simulation with same sample size gt sqrtgamma1gamma1000O 1 4587947eO7 But why use Y N Binomial50 p with p090 and not a much higher p m 1 When p090 a good proportion of X are below 45 and for these simulated values Z X 0 In the latter case nearly all Z would be equal to one would not this lead to smaller variance The answer hinges on the likelihood ratios Consider first this identity relating to likelihood ratios LY 1 LY0109lt LY which is true for all pgt05 We will show that minimizing the highest LY corresponding to positive ZY value ie L45 one also minimizes estimation variance in this setting Let us calculate IS estimator variance V7EEZT 72 ZPyiL2i72 50 Z pXiLi 72 145 Changing the Binomial distribution parameter p utilized in the IS measure affects variance only due to its effect on Li As both p X 139 and Li are decreasing in ithe key to variance reduction is the highest Li value L45 Let us compare L45 values for various p values orp in 79O1120 printpastep1ratiop2pH gt f 1 quot08 637236764452981e 08quot 1 quot081 470875790714497e O8quot 1 quot082 355233842886341e O8quot 1 quot083 273994252590165e O8quot 1 quot084 216437461049284e O8quot g 1 quot085 175465712556885e O8quot i a 1 quot086 146362470828313e O8quot f 1 quot087 126013503845248e O8quot 1 quot088 112427807088493e O8quot 1 quot089 104468772543235e O8quot E 3 1 quot09 1 1 1 H39 g 1 quot091 104815380478361e O8quot 3 1 quot092 115504273091623e O8quot E gquot o 1 quot093 138445017905156e O8quot 1 quot094 184922839271880e O8quot w a a c 1 quot095 285816934625313e O8quot 3 9 1 quot096 544496099936158e 08quot N I I 7 I 1 quot097 143934830672153e o7quot 080 085 090 095 1 quot098 688932752999099e O7quot p 1 quot099 139609978403524e 05quot Indeed minimum L45 and thus variance obtains for p09