Integration of monotone functions of several variables (Q1260657): Difference between revisions

The author studies the approximation of integrals of monotone functions of \(d\) variables. For this purpose he presents algorithms that use evaluations taken at \(n\) points of \([0,1]^ d\) and which approximate the integral \(\int_{[0,1]^ d}f(x)dx\) with minimal error. He shows the following facts: (1) the minimal worst case error is \(O(n^{-1/d})\); (2) the minimal error of randomized methods is \(O(n^{- 1/2-1/d})\); (3) the complexity of approximating integrals of monotone functions with error at most \(\varepsilon\) is \(O(\varepsilon^{-d})\) in the worst case and \(O(\varepsilon^{-2(1+2/d)})\) in the randomized case.