Timeline for How to estimate the accuracy of an integral?
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 1, 2012 at 10:29 | vote | accept | MathematicalOrchid | ||
| Jun 27, 2012 at 6:55 | comment | added | Patrick Caldon | And just to add - this problem could be pretty nasty. "Shaders" are effectively little computational routines. If your function is $f(x) = 0$ if an abstract computer (ie. shader) using a coding of $x$ as its program halts, and $1$ otherwise ... well I would not suggest Monte-Carlo. | |
| Jun 27, 2012 at 6:53 | comment | added | Patrick Caldon | My guess is that your function is probably continuous or differentiable in a lot of places, except at your scene boundaries. Can you identify piecewise differentiable chunks, use quadrature there, and sum the chunks? | |
| Jun 26, 2012 at 20:42 | history | edited | MathematicalOrchid | CC BY-SA 3.0 |
Expand on what I'm asking for.
|
| Jun 26, 2012 at 18:08 | comment | added | whuber♦ | @Macro "Most" functions aren't continuous anywhere! In fact, I do not see how the CLT could possibly apply in general. $f$ could be the inverse CDF of literally any distribution, for instance, in which case your Monte-Carlo draws are sampling from that distribution--for which the CLT need not apply even if the integral itself (i.e., the mean) exists. I think it would be much more fruitful for the OP to narrow the question and respondents to follow jbowman's suggestions. | |
| Jun 26, 2012 at 15:37 | history | edited | StasK |
tag quasi-monte-carlo, monte-carlo, function
|
|
| Jun 26, 2012 at 15:29 | answer | added | StasK | timeline score: 8 | |
| Jun 26, 2012 at 15:27 | comment | added | Macro | @whuber, yes I meant bounded. I agree it is a ridiculously inefficient algorithm but I don't think it's required to know the bounds beforehand - if you had forever to plug in random uniforms, I don't see how the CLT wouldn't apply there. I guess one problem could be having single points of discontinuity in $f$ where it jumps to an extreme value, which would "break" any ability to quantify the error. | |
| Jun 26, 2012 at 15:20 | comment | added | whuber♦ | @Macro That procedure is unrewarding because that's the worst you can do. As jbowman points out, very mild assumptions about $f$ can lead to far better estimates. BTW, it is meaningless to stipulate that $f$ is "finite." If it's a well-defined function, all its values are real numbers and a fortiori finite. If you meant "bounded," that does you no good unless you know the bounds beforehand. | |
| Jun 26, 2012 at 15:16 | comment | added | Macro | @whuber, with only the assumption that $f$ is finite on $(a,b)$ you can a) generate $X$ from a uniform(a,b) distribution, b) calculate $f(X)$ c) repeat $n$ times d) average the results. Then you have an estimate of the integral since it's proportional to $E(f(X))$ and an estimate of the variance ${\rm var}(f(X))/n$, and you can make statements about the error by invoking the central limit theorem. Why do you think that's not rewarding? | |
| Jun 26, 2012 at 15:06 | comment | added | whuber♦ | This has clear but unrewarding answers. The answer to the second question is "nothing": the sole requirement is that $f$ be measurable, which is implicit in asking for its integral. But then the only thing you can do amounts to random sampling. With additional assumptions one can do much better at estimating the integral and assessing the accuracy. So a better question is "what improvements in accuracy estimation can be achieved with which assumptions." But this is overly broad. Therefore, please tell us what kind of functions you are currently dealing with. | |
| Jun 26, 2012 at 15:00 | history | edited | whuber♦ | CC BY-SA 3.0 |
Emphasized the two questions
|
| Jun 26, 2012 at 14:51 | answer | added | Michael R. Chernick | timeline score: 2 | |
| Jun 26, 2012 at 14:48 | comment | added | jbowman | Typically, when you integrate over a known function, you can do much better than Monte Carlo integration. Monte Carlo converges to the true value at a rate of $1/\sqrt{N}$, where $N$ is the number of evaluation points. Other algorithms, e.g., quadrature-based, will converge at a rate $1/N$ or even faster (e.g., for a function that's periodic over the region of integration), assuming some level of smoothness of the function. Still others, based on quasi-random sequences (e.g., Sobol' sequences), will converge at intermediate rates, e.g., $(\ln N)^n/N$ for an $n$-dimensional integration. | |
| Jun 26, 2012 at 14:38 | comment | added | Macro | To the close voters, it appears that this problem is about monte carlo integration based on the statement "So we want to choose several x-values at random, and stop when the estimate for k becomes acceptably accurate." which seems distinctly on topic since it involves random number generation/sampling, and parameter estimation so I'm not quite sure what the rationale for the "off topic" votes is. | |
| Jun 26, 2012 at 14:34 | comment | added | Macro | When you say "if we know absolutely nothing about $f$", what do you mean exactly? We can calculate $f$, right? | |
| Jun 26, 2012 at 13:34 | history | tweeted | twitter.com/#!/StackStats/status/217611778950049792 | ||
| Jun 26, 2012 at 10:44 | history | edited | chl | CC BY-SA 3.0 |
edited title
|
| Jun 26, 2012 at 10:40 | history | asked | MathematicalOrchid | CC BY-SA 3.0 |