Quasi-Monte Carlo Method - Approximation Error Bounds of Quasi-Monte Carlo

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:

    “Truth is the kind of error without which a certain species of life could not live. The value for life is ultimately decisive.”
    —Friedrich Nietzsche (1844–1900)

    “Firmness yclept in heroes, kings and seamen,
    That is, when they succeed; but greatly blamed
    As obstinacy, both in men and women,
    Whene’er their triumph pales, or star is tamed —
    And ‘twill perplex the casuist in morality
    To fix the due bounds of this dangerous quality.”
    —George Gordon Noel Byron (1788–1824)

    “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)