Josef Leydold: Some remarks on F-discrepancy, numerical inversion and integration error

This is a joint work with Wolfgang Hörmann.

There are situations in quasi-Monte Carlo integration where non-uniform low discrepancy point sets are required. Generally the inversion method (implicitly or explicitly applied) is used to transform the uniform low discrepancy point set into the non-uniform one. For most distributions only (slow) numerical methods are available for inversion which leads to approximation errors which can be expressed in terms of the F-discrepancy (discrepancy from the distribution with given c.d.f. F). Another problem occurs if the given distribution has unbounded domain as this leads to an integrand with unbounded variation. In this case additional conditions on the integrand and on the underlying low discrepancy set are necessary (see e.g. [3]). Alternatively, a special design of the transformation method (like those introduced by Hlawka [1]) can omit such problems. In this short note we show that an approximation of the inverse distribution function by cubic Hermite interpolation [3] is a very fast method to generate low discrepancy point sets with the necessary properties.


E. Hlawka.
Gleichverteilung und Simulation.
Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II, 206:183-216, 1997.

Josef Leydold and Wolfgang Hörmann.
Continuous random variate generation by fast numerical inversion.
ACM TOMACS, 13:347-362, 2003.

Art B. Owen.
Halton sequences avoid the origin.
(preprint available at owen/reports/halton.pdf).

Back to the Index

Please send comments and corrections to Thomas Klausner.