Discrepancy

In the previous section, the term equidistributed point set was used without defining equidistribution. An assessment of distribution quality needs a suitable measure. The classical measure in the theory of uniform distribution is discrepancy, which in a certain sense measures the deviation of a point set from an ideal distribution.

We will introduce a special form of discrepancy, the so-called star-discrepancy. Consider a point set , in the -dimensional unit cube . The star-discrepancy of is defined as

and denotes the class of all multidimensional subintervals of of the form , where and . Hence, the star-discrepancy is attained for a (half-open) subinterval of with the left corner in the origin (see Figure 3 for some discrete examples ) providing maximal deviation of the relative number of points within the interval from its volume . The number is called local discrepancy.

The measure may also be seen as a number-theoretical adaptation of a well-known goodness-of-fit test in statistics, the two-sided Kolmogorov-Smirnov test that is used to test the hypothesis that a sample stems from a particular continuous probability distribution. In our case, the target distribution is the uniform distribution on .

The computation of discrepancy is very time consuming with a complexity of for points in the -dimensional unit cube. Hence, an assessment of uniform distribution is usually achieved by theoretical discrepancy estimates or by an application of several other measures of equidistribution, which, although they are easier to compute, are sometimes not that intuitive.

Furthermore, every numerical application of uniformly distributed point sets works with finite precision numbers. Therefore, it is important to apply discrepancy for finite precision subintervals (see Figure 3 for some examples). This leads to the concept of discrete discrepancy [3], which is defined in the same way as in equation (3), but now denotes the class of all (discrete) subintervals of the form , where , with integers .

The DiscreteDiscrepancy[p,m] function gives a list of local discrepancies for all discrete intervals with resolution and a given point set . To calculate this function, we represent the intervals by the list of endpoints , , , and use simple list operations.

The following matrix shows the output of DiscreteDiscrepancy[,3]. The value at position equals local discrepancy for the interval with endpoints .

Discrete discrepancy is the maximum of the matrix, . In our example, the maximum is attained for two intervals with endpoints and . As one may guess, calculating DiscreteDiscrepancy[p,m] in this simple way becomes very difficult for increasing . However, we can use this function to analyze the structure of local discrepancy for small point sets in order to gain elementary information for a subsequent theoretical discrepancy estimation of larger point sets. This very useful strategy allowed the author to construct a method to estimate the star-discrepancy of arbitrary nets [7].