TOPICS
Search

Discrepancy Theorem


Let s_1, s_2, ... be an infinite series of real numbers lying between 0 and 1. Then corresponding to any arbitrarily large K, there exists a positive integer n and two subintervals of equal length such that the number of s_nu with nu=1, 2, ..., n which lie in one of the subintervals differs from the number of such s_nu that lie in the other subinterval by more than K (van der Corput 1935ab, van Aardenne-Ehrenfest 1945, 1949, Roth 1954).

This statement can be refined as follows. Let N be a large integer and s_1, s_2, ..., s_N be a sequence of N real numbers lying between 0 and 1. Then for any integer 1<=n<=N and any real number alpha satisfying 0<alpha<1, let D_n(alpha) denote the number of s_nu with nu=1, 2, ..., n that satisfy 0<=s_nu<alpha. Then there exist n and alpha such that

 |D_n(alpha)-nalpha|>c_1(lnlnN)/(lnlnlnN)
(1)

where c_1 is a positive constant. Schmidt (1972) improved upon this result to obtain

 |D_n(alpha)-nalpha|>lnN/100,
(2)

which is essentially optimal.

DiscrepancyTheorem

This result can be further strengthened, which is most easily done by reformulating the problem. Let N>1 be an integer and P_1, P_2, ..., P_N be N (not necessarily distinct) points in the square 0<=x<=1, 0<=y<=1. Then

 int_0^1int_0^1[S(x,y)-Nxy]^2dxdy>c_2lnN,
(3)

where c_2 is a positive constant and S(u,v) is the number of points in the rectangle 0<=x<u, 0<=y<v (Roth 1954). Therefore,

 |S(x,y)-Nxy|>c_3sqrt(lnN),
(4)

and the original result can be stated as the fact that there exist n and alpha such that

 |D_n(alpha)-nalpha|>c_4sqrt(lnN).
(5)

The randomly distributed points shown in the above squares have |S(x,y)-Nxy|^2=6.40 and 9.11, respectively.

Similarly, the discrepancy of a set of N points in a unit d-hypercube satisfies

 |S(x,y)-Nxy|>c(lnN)^((d-1)/2)
(6)

(Roth 1954, 1976, 1979, 1980).


See also

18-Point Problem, Cube Point Picking, Discrepancy

Explore with Wolfram|Alpha

References

Berlekamp, E. R. and Graham, R. L. "Irregularities in the Distributions of Finite Sequences." J. Number Th. 2, 152-161, 1970.Roth, K. F. "On Irregularities of Distribution." Mathematika 1, 73-79, 1954.Roth, K. F. "On Irregularities of Distribution. II." Comm. Pure Appl. Math. 29, 739-744, 1976.Roth, K. F. "On Irregularities of Distribution. III." Acta Arith. 35, 373-384, 1979.Roth, K. F. "On Irregularities of Distribution. IV." Acta Arith. 37, 67-75, 1980.Schmidt, W. M. "Irregularities of Distribution. VII." Acta Arith. 21, 45-50, 1972.van Aardenne-Ehrenfest, T. "Proof of the Impossibility of a Just Distribution of an Infinite Sequence Over an Interval." Proc. Kon. Ned. Akad. Wetensch. 48, 3-8, 1945.van Aardenne-Ehrenfest, T. Proc. Kon. Ned. Akad. Wetensch. 52, 734-739, 1949.van der Corput, J. G. Proc. Kon. Ned. Akad. Wetensch. 38, 813-821, 1935a.van der Corput, J. G. Proc. Kon. Ned. Akad. Wetensch. 38, 1058-1066, 1935b.

Referenced on Wolfram|Alpha

Discrepancy Theorem

Cite this as:

Weisstein, Eric W. "Discrepancy Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DiscrepancyTheorem.html

Subject classifications