Low-discrepancy Sequence - Lower Bounds

Lower Bounds

Let s = 1. Then

D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2N}

for any finite point set {x1, ..., xN}.

Let s = 2. W. M. Schmidt proved that for any finite point set {x1, ..., xN},

D_N^*(x_1,\ldots,x_N)\geq C\frac{\log N}{N}

where

C=\max_{a\geq3}\frac{1}{16}\frac{a-2}{a\log a}=0.023335\dots

For arbitrary dimensions s > 1, K.F. Roth proved that

D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2^{4s}}\frac{1}{((s-1)\log2)^\frac{s-1}{2}}\frac{\log^{\frac{s-1}{2}}N}{N}

for any finite point set {x1, ..., xN}. This bound is the best known for s > 3.

Read more about this topic:  Low-discrepancy Sequence

Famous quotes containing the word bounds:

    “How far men go for the material of their houses! The inhabitants of the most civilized cities, in all ages, send into far, primitive forests, beyond the bounds of their civilization, where the moose and bear and savage dwell, for their pine boards for ordinary use. And, on the other hand, the savage soon receives from cities iron arrow-points, hatchets, and guns, to point his savageness with.”
    —Henry David Thoreau (1817–1862)

    “Great Wits are sure to Madness near alli’d
    And thin Partitions do their Bounds divide;
    Else, why should he, with Wealth and Honour blest,
    Refuse his Age the needful hours of Rest?”
    —John Dryden (1631–1700)