Approximation Error Bounds of Quasi-Monte Carlo
The approximation error of the quasi-Monte Carlo method is bounded by a term proportional to the discrepancy of the set x1, ..., xN. Specifically, the Koksma-Hlawka inequality states that the error
is bounded by
- ,
where V(f) is the Hardy-Krause variation of the function f (see Morokoff and Caflisch (1995) for the detailed definitions). DN is the discrepancy of the set (x1,...,xN) and is defined as
- ,
where Q is a rectangular solid in s with sides parallel to the coordinate axes. The inequality can be used to show that the error of the approximation by the quasi-Monte Carlo method is, whereas the Monte Carlo method has a probabilistic error of . Though we can only state the upper bound of the approximation error, the convergence rate of quasi-Monte Carlo method in practice is usually much faster than its theoretical bound. Hence, in general, the accuracy of the quasi-Monte Carlo method increases faster than that of the Monte Carlo method.
Read more about this topic: Quasi-Monte Carlo Method
Famous quotes containing the words error, bounds and/or carlo:
“Never miss an opportunity to allow a child to do something she can and wants to on her own. Sometimes we’re in too much of a rush—and she might spill something, or do it wrong. But whenever possible she needs to learn, error by error, lesson by lesson, to do better. And the more she is able to learn by herself the more she gets the message that she’s a kid who can.”
—Polly Berrien Berends (20th century)
“How far men go for the material of their houses! The inhabitants of the most civilized cities, in all ages, send into far, primitive forests, beyond the bounds of their civilization, where the moose and bear and savage dwell, for their pine boards for ordinary use. And, on the other hand, the savage soon receives from cities iron arrow-points, hatchets, and guns, to point his savageness with.”
—Henry David Thoreau (1817–1862)
“If there is anything so romantic as that castle-palace-fortress of Monaco I have not seen it. If there is anything more delicious than the lovely terraces and villas of Monte Carlo I do not wish to see them. There is nothing beyond the semi-tropical vegetation, the projecting promontories into the Mediterranean, the all-embracing sweep of the ocean, the olive groves, and the enchanting climate! One gets tired of the word beautiful.”
—M. E. W. Sherwood (1826–1903)