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:

    “Firmness yclept in heroes, kings and seamen,
    That is, when they succeed; but greatly blamed
    As obstinacy, both in men and women,
    Whene’er their triumph pales, or star is tamed —
    And ‘twill perplex the casuist in morality
    To fix the due bounds of this dangerous quality.”
    —George Gordon Noel Byron (1788–1824)

    “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)