Monte Carlo integration is a method of estimating definite integrals by means of Monte Carlo simulation. Consider computing the area of a region of space described by a predicate
that is true for points
in the region and false for points not in the region. For example, the region contained within a circle of radius
is described by the predicate that tests whether
(x - 5)² + (y - 7)² ≤ 3²
. To estimate the area of the region described by such a predicate, begin by choosing a rectangle that contains the region. For example, a rectangle with diagonally opposite corners at
contains the circle above. The desired integral is the area of that portion of the rectangle that lies in the region. We can estimate the integral by picking, at random, points
that lie in the rectangle, and testing
for each point to determine whether the point lies in the region. If we try this with many points, then the fraction of points that fall in the region should give an estimate of the proportion of the rectangle that lies in the region. Hence, multiplying this fraction by the area of the entire rectangle should produce an estimate of the integral.
Implement Monte Carlo integration as a procedure
that takes as arguments a predicate
, upper and lower bounds
x1, x2, y1
for the rectangle, and the number of trials to perform in order to produce the estimate. Your procedure should use the same
procedure that was used above to estimate
. Use your
to produce an estimate of
by measuring the area of a unit circle.
You will find it useful to have a procedure that returns a number chosen at random from a given range. The following
procedure implements this in terms of the
procedure used in section
, which returns a nonnegative number less than its input.
(define (random-in-range low high) (let ((range (- high low))) (+ low (random range))))
There are no comments yet.
You must log in to post a comment.Login
(define (monte-carlo trials experiment) (define (iter trials-remaining trials-passed) (cond ((= trials-remaining 0) (/ trials-passed trials)) ((experiment) (iter (- trials-remaining 1) (+ trials-passed 1))) (else (iter (- trials-remaining 1) trials-passed)))) (iter trials 0)) (define (random-in-range low high) (let ((range (- high low))) (+ low (random range)))) (define (square x) (* x x)) (define (square-predicate? x y) (< (+ (square x) (square y)) 1.0)) (define (test-pi trials) (exact->inexact (estimate-integral square-predicate? -1.0 1.0 -1.0 1.0 trials))) (check-equal? (floor (* 10 (test-pi 1000))) 31.0) (check-equal? (floor (* 10 (test-pi 10000))) 31.0)