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)

    “At bounds of boundless void.”
    —Samuel Beckett (1906–1989)