Problem 179. Monte-Carlo integration

Created by Tomasz

Solve Later

Write a function that estimates a d-dimensional integral to at least 1% relative precision.

Inputs:

d: positive integer. The dimension of the integral.
fun: function handle. The function accepts a row-vector of length d as an argument and returns a real scalar as a result.

Output:

I: is the integral over fun from 0 to 1 in each direction.

     1     1        1            
     /     /        /           
 I = |dx_1 |dx_2 ...| dx_d  fun([x_1,x_2,...,x_d])
     /     /        /            
     0     0        0

Example:

fun = @(x) x(1)*x(2)
d = 2

The result should be 0.25. An output I=0.2501 would be acceptable, because the relative deviation would be abs(0.25-0.2501)/0.25 which is smaller than 1%.

The functions in the test-suite are all positive and generally 'well behaved', i.e. not fluctuating too much. Some of the tests hav a relatively large d.

Solve

Solution Stats

Last solution submitted on Aug 08, 2019

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

the cyclist on 1 Feb 2012

I'm confused by the 3rd test case. Can the integral inside an n-dimensional hypercube really be greater than 1?

the cyclist on 1 Feb 2012

In my comment, I mean an n-dimensional UNIT hypercube, which is what you integration limits impose.

Tomasz on 1 Feb 2012

Of course. It depends on the integrand. Even in 1d, if the integrand is e.g. 10x, the result will be 5.

the cyclist on 1 Feb 2012

I was confused. Thanks for clarifying.

David Verrelli on 1 Jul 2018

I found it helpful to think about the problem as involving d+1 dimensions: the d dimensions of the input variables, and one more dimension for the (scalar) output variable. —DIV

Solution Comments

Solution 556220

3 Comments

3 Comments

David Verrelli on 2 Jul 2018

Innovative, but a bit risky/lucky: roughly a 20–30% risk of failing the Test Suite, by my estimation [see Solutions 1572717–1572721, and Solution 1572713; cf. Solution 1572418].

Tomasz on 3 Jul 2018

Since the Monte-Carlo errors decrease proportionally to 1/sqrt(N), where N is the number of random numbers, you should always be able to choose a large enough N to nearly always pass the tests. This is only limited by the execution-time limit that cody enforces.

David Verrelli on 27 Jun 2019

I agree that it is possible to choose N in such a way as to be practically guaranteed to pass the Test Suite. My point is that in this submission (and BTW also in Solution 188645) N has been chosen smaller than that, and so some luck was needed for this submission to pass — there was a significant risk that it could have failed.

Solution 16892

2 Comments

2 Comments

@bmtran (Bryant Tran) on 30 Jan 2012

just found this "cheat". don't hate! I've reported it to TMW

Tomasz on 30 Jan 2012

I adjusted the test suite, thanks for the hint...