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

157 Solutions
57 Solvers

Last Solution submitted on Sep 03, 2020

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

Problem Recent Solvers57

Problem Tags

monte-carlo integration rand

Problem 179. Monte-Carlo integration

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers57

Suggested Problems

More from this Author7

Problem Tags

Problem 179. Monte-Carlo integration

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers57

Suggested Problems

More from this Author7

Problem Tags

Players