Difference between revisions of "Discrepancy"
m (gather refs) |
|||
Line 72: | Line 72: | ||
<TR><TD valign="top">[7]</TD> <TD valign="top"> I.M. Sobol', "The distribution of points in a cube and the approximate evaluation of integrals" ''USSR Comp. Math. and Math. Phys.'' , '''7''' : 4 (1967) pp. 86–112 ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''7''' : 4 (1967) pp. 784–802</TD></TR> | <TR><TD valign="top">[7]</TD> <TD valign="top"> I.M. Sobol', "The distribution of points in a cube and the approximate evaluation of integrals" ''USSR Comp. Math. and Math. Phys.'' , '''7''' : 4 (1967) pp. 86–112 ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''7''' : 4 (1967) pp. 784–802</TD></TR> | ||
<TR><TD valign="top">[8]</TD> <TD valign="top"> N.M. Korobov, "Number-theoretical methods in approximate analysis" , Moscow (1963) (In Russian)</TD></TR> | <TR><TD valign="top">[8]</TD> <TD valign="top"> N.M. Korobov, "Number-theoretical methods in approximate analysis" , Moscow (1963) (In Russian)</TD></TR> | ||
− | <TR><TD valign="top">[9]</TD> <TD valign="top"> L. Kuipers, H. Niederreiter, "Uniform distribution of sequences" , Wiley (1974) {{ZBL|0281.10001}}; repr. Dover (2006) ISBN 0-486-45019-8 </TD></TR> | + | <TR><TD valign="top">[9]</TD> <TD valign="top"> L. Kuipers, H. Niederreiter, "Uniform distribution of sequences" , Wiley (1974) {{ZBL|0281.10001}}; repr. Dover (2006) {{ISBN|0-486-45019-8}} </TD></TR> |
<TR><TD valign="top">[a1]</TD> <TD valign="top"> J. Beck, W.L. Chen, "Irregularities of distribution" , Cambridge Univ. Press (1987) {{ZBL|0617.10039}}</TD></TR> | <TR><TD valign="top">[a1]</TD> <TD valign="top"> J. Beck, W.L. Chen, "Irregularities of distribution" , Cambridge Univ. Press (1987) {{ZBL|0617.10039}}</TD></TR> | ||
</table> | </table> | ||
{{TEX|done}} | {{TEX|done}} |
Latest revision as of 15:35, 8 October 2023
of a sequence of points from the unit s-dimensional cube K_s = \{\mathbf{x} : 0 \le x_\nu < 1\,,\ \nu=1,\ldots,s \}
The norm of the functional \begin{equation}\label{eq:1} \phi(\alpha;\omega) = |V| - \frac{N(V)}{N}\,, \end{equation} calculated in some metric. Here, |V| and N(V) are, respectively, the volume of the domain V = \{\mathbf{x} : 0 \le x_\nu < \alpha_\nu\,,\ \nu=1,\ldots,s \} and the number of the points of \omega belonging to V. If one considers the distribution of the points of \omega over domains of the type V = \{\mathbf{x} : \alpha_\nu \le x_\nu < \beta_\nu\,,\ \nu=1,\ldots,s \}, then, in formula (1), \phi(\alpha;\omega) is usually replaced by \phi(\alpha,\beta;\omega).
The following norms of the functional \eqref{eq:1} are most often used: D_N(\omega) = \sup_{\alpha,\beta\in K_s} |\phi(\alpha,\beta;\omega)|\ , D_N^*(\omega) = \sup_{\alpha\in K_s} |\phi(\alpha;\omega)|\ , D_N(\omega,L_p) = \left({ \int_0^1\cdots\int_0^1 |\phi(\alpha;\omega)|^p d\alpha_1\ldots d\alpha_s }\right)^{1/p} \ .
A sequence \omega=(\mathbf{x}_1,\ldots,\mathbf{x}_N,\ldots) of points from the s-dimensional unit cube K_s is uniformly distributed if and only if [1] \lim_{N\rightarrow\infty} D_N(\omega) = 0 \ .
For any infinite sequence \omega=(x_1,\ldots,x_N,\ldots) of one-dimensional points the following theorem [3] is valid: \limsup N D_N(\omega) = \infty \ . For any such sequence \omega it is possible to find a sequence N_1,\ldots,N_k,\ldots such that for N = N_k one has [4], N D_N(\omega) > C_1 \sqrt{\log N} \ . The final result [5] for infinite sequences of one-dimensional points is that for N = N_k: N D_N(\omega) > C_2 \log N \ .
Studies were made of the discrepancies of various concrete sequences [6]–[8], and the estimates from above N D_N(\omega,L_2) \le C_3(s) \log^{s+1} N \ , N D_N(\omega) \le C_4(s) \log^s N were obtained, respectively, for finite and infinite sequences, as well as an estimate from below [4]: For any sequence of N points, the following inequality is valid: N D_N(\omega,L_2) \ge C_5(s) \log^{(s+1)/2} N \ .
For any infinite sequence \omega = \{\mathbf{x}_n \in K_s \} it is possible to find a sequence of numbers N_1,\ldots,N_k,\ldots such that for N = N_k one has N D_N(\omega,L_2) \ge C_6(s) \log^{s/2} N \ .
Also, D_N(\omega) \ge D_N(\omega,L_2) \ .
Comments
See also Distribution modulo one; Distribution modulo one, higher-dimensional; Uniform distribution.
References
[1] | H. Weyl, "Ueber die Gleichverteilung von Zahlen mod Eins" Math. Ann. , 77 (1916) pp. 313–352 |
[2] | J.G. van der Corput, "Verteilungsfunktionen" Proc. Koninkl. Ned. Akad. Wet. A , 38 : 8 (1935) pp. 813–821; 1058–1066 |
[3] | T. van Aardenne-Ehrenfest, "On the impossibility of a just distribution" Indag. Math. , 11 (1949) pp. 264–269 |
[4] | K.F. Roth, "On irregularities of distribution" Mathematika , 1 (1954) pp. 73–79 Zbl 0057.28604 |
[5] | W.M. Schmidt, "Irregularities of distribution VII" Acta Arithm. , 21 (1972) pp. 45–50 |
[6] | J.H. Halton, "On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals" Numer. Math. , 2 : 2 (1960) pp. 84–90 |
[7] | I.M. Sobol', "The distribution of points in a cube and the approximate evaluation of integrals" USSR Comp. Math. and Math. Phys. , 7 : 4 (1967) pp. 86–112 Zh. Vychisl. Mat. i Mat. Fiz. , 7 : 4 (1967) pp. 784–802 |
[8] | N.M. Korobov, "Number-theoretical methods in approximate analysis" , Moscow (1963) (In Russian) |
[9] | L. Kuipers, H. Niederreiter, "Uniform distribution of sequences" , Wiley (1974) Zbl 0281.10001; repr. Dover (2006) ISBN 0-486-45019-8 |
[a1] | J. Beck, W.L. Chen, "Irregularities of distribution" , Cambridge Univ. Press (1987) Zbl 0617.10039 |
Discrepancy. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Discrepancy&oldid=53569