Linear Time Estimators for Assessing Uniformity of Point Samples in Hypercubes
Volume 27, Issue 2 (2016), pp. 335–349
Pub. online: 1 January 2016
Type: Research Article
Received
1 February 2016
1 February 2016
Accepted
1 May 2016
1 May 2016
Published
1 January 2016
1 January 2016
Abstract
We investigate the problem of detecting a point set’s deviation from uniformity in the unit hypercube. High uniformity is for example desirable in Monte Carlo methods for numerical integration, but also for obtaining a good worst-case bound in global optimization. In high dimensions, many points are required to get reliable results, so the point sets are preferably generated by fast methods such as quasirandom sequences. Unfortunately, assessing their uniformity often requires quadratic time. So, we present several numerical summary characteristics of point sets that can be computed in linear time. They do not measure uniformity directly, but by comparing them to reference values for the uniform distribution, deviations from uniformity can be quickly detected. The necessary reference values are also derived here, if possible exactly, else approximately.