Monte Carlo Method(2
Monte Carlo Method (2)
Monte Carlo Integration Hit and miss method. ndrg(x) g(x) When-d g(x)c, we can al ways first make a shift f(x=g(x)+d so that f(x) 0 algorithm )generate n uniform random numbers, 5i(i=1, 2, .. N), on(a, b) and n uniform random numbers, Si(i-1, 2,..., N), on(0,c) 2)calculate g(si) and count the number of cases, Nhit, for which g(25) 3)I can be estimated by 5-S3, (b-a Hit/N
Monte Carlo Integration Hit and miss method: = b a I dxg(x) When -d g(x) c, we can always first make a shift f(x)=g(x)+d so that f(x) 0. Algorithm: 1) generate N uniform random numbers, i (i=1,2,…,N), on (a,b) and N uniform random numbers, i (i=1,2,…,N), on (0,c); 2) calculate g(i ) and count the number of cases, Nhit, for which i < g(i ); 3) I can be estimated by Iest=c(b-a)Nhit/N 0 g(x) c
Geometrical illustration glx o mIss N c(b gIX hit a Variance var(L-(b-a]var(p=c(b-a)-I Remark NL has a binomial distribution evar( lest) increases with c(b-a)-I(i.e, the numerical error of the method increases with c(b-a)-1)
Geometrical illustration: c a b x g(x) g(x) miss hit ( ) ( ) ˆ c b a dxg x p b hit a N N − = = Variance: c b a I N I c b a p I est var( )= ( − ) var(ˆ)= ( − )− 2 Remark: •Nhit has a binomial distribution. •var(Iest) increases with c(b-a)-I (i.e., the numerical error of the method increases with c(b-a)-I)
Simple Mean-value Method: 1=dxg(x) -(b-a)dxg(x)ba (b-axg(x) Remark <g(x)> is the mean value of g(x) for a uniform random distribution on(a, b) Algorithm .generate N random numbers, X;, distributed uniformly on(a, b) i can be estimated by using In=2x2∑(x) Variance (b-a) (6 var( var 28(x 2 var(>8(x) var(glx )) (b-a]dxg(xI
Simple Mean-Value Method: Remark: <g(x)> is the mean value of g(x) for a uniform random distribution on (a, b). Algorithm: •generate N random numbers, xi , distributed uniformly on (a, b); •I can be estimated by using, ( ) ( ) 1 ( ) ( ) ( ) b a g x b a I dxg x b a dxg x b a b a = − − = = − = − = N i I est xi g N b a 1 ( ) Variance: ( ) var( ( )) var( ( )) ( ) var( ) var ( ) ( ) 2 1 2 2 1 x N b a x N b a I g x g g N b a N i i N i est i − − = = − = = = = − − b a g I b a dx x N 2 2 ( ) ( ) 1
Efficiency of Monte Carlo Integration Smaller is the variance of the estimated result, higher is the efficiency of the method illustration var est 1/N For fixed n. smaller variance leads to smaller calculation error est large variance smal variance
Efficiency of Monte Carlo Integration Smaller is the variance of the estimated result, higher is the efficiency of the method. Illustration: var(Iest)~1/N For fixed N, smaller variance leads to smaller calculation error. N Iest I N Iest I large variance small variance