Families of Well Approximable Measures

We provide an algorithm to approximate a finitely supported discrete measure μby a measure νNcorresponding to a set of Npoints so that the total variation between μand νNhas an upper bound. As a consequence if μis a (finite or infinitely supported) discrete probability measure on [0, 1]d with a sufficient decay rate on the weights of each point, then μcan be approximated by νNwith total variation, and hence star-discrepancy, bounded above by (log N)N−1. Our result improves, in the discrete case, recent work by Aistleitner, Bilyk, and Nikolov who show that for any normalized Borel measure μ, there exist finite sets whose star-discrepancy with respect to μis at most (logN)d−12N−1{\left( {\log \,N} \right)^{d - {1 \over 2}}}{N^{ - 1}}. Moreover, we close a gap in the literature for discrepancy in the case d=1 showing both that Lebesgue is indeed the hardest measure to approximate by finite sets and also that all measures without discrete components have the same order of discrepancy as the Lebesgue measure.