Problem 179. Monte-Carlo integration

Created by Tomasz

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a function that estimates a d-dimensional integral to at least 1% relative precision.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Inputs:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>d: positive integer. The dimension of the integral.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>fun: function handle. The function accepts a row-vector of length d as an argument and returns a real scalar as a result.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>I: is the integral over fun from 0 to 1 in each direction.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[     1     1        1            \n     /     /        /           \n I = |dx_1 |dx_2 ...| dx_d  fun([x_1,x_2,...,x_d])\n     /     /        /            \n     0     0        0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[fun = @(x) x(1)*x(2)\nd = 2]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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%.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

250 Solutions
49 Solvers

Last Solution submitted on Nov 20, 2022

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 2906932

1 Comment

1 Comment

Muhammet Fatih isik on 14 May 2021

Hi sir, could u share ur solution with me cause I attempt nearly 50 times and still ain't got to complate. I don't know where is the problem and it's frustrating.

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 188645

1 Comment

1 Comment

Huihui Li on 5 Oct 2022

Nice solution!

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...

Problem Recent Solvers49

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 179. Monte-Carlo integration

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers49

Suggested Problems

More from this Author7

Problem Tags

Community Treasure Hunt

Problem 179. Monte-Carlo integration

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers49

Suggested Problems

More from this Author7

Problem Tags

Community Treasure Hunt

Players