In
mathematics, a
sequence (''s''
1, ''s''
2, ''s''
3, ...) of
real numbers is said to be equidistributed, or uniformly distributed, if the proportion of terms falling in a subinterval is proportional to the length of that subinterval. Such sequences are studied in
Diophantine approximation theory and have applications to
Monte Carlo integration.
Definition
A sequence (''s''
1, ''s''
2, ''s''
3, ...) of
real numbers is said to be ''equidistributed'' on a non-degenerate
interval 'a'', ''b''if for every subinterval
'c'', ''d''of
'a'', ''b''we have
:
(Here, the notation , ∩
'c'', ''d'' denotes the number of elements, out of the first ''n'' elements of the sequence, that are between ''c'' and ''d''.)
For example, if a sequence is equidistributed in
, 2 since the interval
.5, 0.9occupies 1/5 of the length of the interval
, 2 as ''n'' becomes large, the proportion of the first ''n'' members of the sequence which fall between 0.5 and 0.9 must approach 1/5. Loosely speaking, one could say that each member of the sequence is equally likely to fall anywhere in its range. However, this is not to say that (''s''
''n'') is a sequence of
random variables; rather, it is a determinate sequence of real numbers.
Discrepancy
We define the discrepancy ''D''
''N'' for a sequence (''s''
1, ''s''
2, ''s''
3, ...) with respect to the interval
'a'', ''b''as
:
A sequence is thus equidistributed if the discrepancy ''D''
''N'' tends to zero as ''N'' tends to infinity.
Equidistribution is a rather weak criterion to express the fact that a sequence fills the segment leaving no gaps. For example, the drawings of a random variable uniform over a segment will be equidistributed in the segment, but there will be large gaps compared to a sequence which first enumerates multiples of ε in the segment, for some small ε, in an appropriately chosen way, and then continues to do this for smaller and smaller values of ε. For stronger criteria and for constructions of sequences that are more evenly distributed, see
low-discrepancy sequence.
Riemann integral criterion for equidistribution
Recall that if ''f'' is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
having a
Riemann integral in the interval
'a'', ''b'' then its integral is the limit of
Riemann sum
In mathematics, a Riemann sum is a certain kind of approximation of an integral by a finite sum. It is named after nineteenth century German mathematician Bernhard Riemann. One very common application is approximating the area of functions or li ...
s taken by sampling the function ''f'' in a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of points chosen from a fine partition of the interval. Therefore, if some sequence is equidistributed in
'a'', ''b'' it is expected that this sequence can be used to calculate the integral of a Riemann-integrable function. This leads to the following criterion for an equidistributed sequence:
Suppose (''s''
1, ''s''
2, ''s''
3, ...) is a sequence contained in the interval
'a'', ''b'' Then the following conditions are equivalent:
# The sequence is equidistributed on
'a'', ''b''
# For every Riemann-integrable (
complex-valued
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
) function , the following limit holds:
::
:
This criterion leads to the idea of
Monte-Carlo integration, where integrals are computed by sampling the function over a sequence of random variables equidistributed in the interval.
It is not possible to generalize the integral criterion to a class of functions bigger than just the Riemann-integrable ones. For example, if the
Lebesgue integral
In mathematics, the integral of a non-negative function of a single variable can be regarded, in the simplest case, as the area between the graph of that function and the -axis. The Lebesgue integral, named after French mathematician Henri Le ...
is considered and ''f'' is taken to be in
''L''1, then this criterion fails. As a counterexample, take ''f'' to be the
indicator function of some equidistributed sequence. Then in the criterion, the left hand side is always 1, whereas the right hand side is zero, because the sequence is
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
, so ''f'' is zero
almost everywhere
In measure theory (a branch of mathematical analysis), a property holds almost everywhere if, in a technical sense, the set for which the property holds takes up nearly all possibilities. The notion of "almost everywhere" is a companion notion to ...
.
In fact, the de Bruijn–Post Theorem states the converse of the above criterion: If ''f'' is a function such that the criterion above holds for any equidistributed sequence in
'a'', ''b'' then ''f'' is Riemann-integrable in
'a'', ''b''
Equidistribution modulo 1
A sequence (''a''
1, ''a''
2, ''a''
3, ...) of real numbers is said to be equidistributed modulo 1 or uniformly distributed modulo 1 if the sequence of the
fractional part
The fractional part or decimal part of a non‐negative real number x is the excess beyond that number's integer part. If the latter is defined as the largest integer not greater than , called floor of or \lfloor x\rfloor, its fractional part can ...
s of ''a''
''n'', denoted by (''a''
''n'') or by ''a''
''n'' − ⌊''a''
''n''⌋, is equidistributed in the interval
, 1
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
Examples
* The
equidistribution theorem
In mathematics, the equidistribution theorem is the statement that the sequence
:''a'', 2''a'', 3''a'', ... mod 1
is uniformly distributed on the circle \mathbb/\mathbb, when ''a'' is an irrational number. It is a special case of the ergodi ...
: The sequence of all multiples of an
irrational ''α'',
::0, ''α'', 2''α'', 3''α'', 4''α'', ...
:is equidistributed modulo 1.
[Kuipers & Niederreiter (2006) p. 8]
* More generally, if ''p'' is a
polynomial with at least one coefficient other than the constant term irrational then the sequence ''p''(''n'') is uniformly distributed modulo 1.
This was proven by Weyl and is an application of van der Corput's difference theorem.
[Kuipers & Niederreiter (2006) p. 27]
* The sequence log(''n'') is ''not'' uniformly distributed modulo 1.
[ This fact is related to ]Benford's law
Benford's law, also known as the Newcomb–Benford law, the law of anomalous numbers, or the first-digit law, is an observation that in many real-life sets of numerical data, the leading digit is likely to be small.Arno Berger and Theodore ...
.
* The sequence of all multiples of an irrational ''α'' by successive prime numbers,
::2''α'', 3''α'', 5''α'', 7''α'', 11''α'', ...
:is equidistributed modulo 1. This is a famous theorem of analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Diri ...
, published by I. M. Vinogradov in 1948.[Kuipers & Niederreiter (2006) p. 129]
* The van der Corput sequence is equidistributed.[Kuipers & Niederreiter (2006) p. 127]
Weyl's criterion
Weyl's criterion states that the sequence ''a''''n'' is equidistributed modulo 1 if and only if for all non-zero integers ℓ,
:
The criterion is named after, and was first formulated by, Hermann Weyl. It allows equidistribution questions to be reduced to bounds on exponential sum
In mathematics, an exponential sum may be a finite Fourier series (i.e. a trigonometric polynomial), or other finite sum formed using the exponential function, usually expressed by means of the function
:e(x) = \exp(2\pi ix).\,
Therefore, a typic ...
s, a fundamental and general method.
:
Generalizations
* A quantitative form of Weyl's criterion is given by the Erdős–Turán inequality.
* Weyl's criterion extends naturally to higher dimensions, assuming the natural generalization of the definition of equidistribution modulo 1:
The sequence ''v''''n'' of vectors in R''k'' is equidistributed modulo 1 if and only if for any non-zero vector ℓ ∈ Z''k'',
:
Example of usage
Weyl's criterion can be used to easily prove the equidistribution theorem
In mathematics, the equidistribution theorem is the statement that the sequence
:''a'', 2''a'', 3''a'', ... mod 1
is uniformly distributed on the circle \mathbb/\mathbb, when ''a'' is an irrational number. It is a special case of the ergodi ...
, stating that the sequence of multiples 0, ''α'', 2''α'', 3''α'', ... of some real number ''α'' is equidistributed modulo 1 if and only if ''α'' is irrational.[
Suppose ''α'' is irrational and denote our sequence by ''a''''j'' = ''jα'' (where ''j'' starts from 0, to simplify the formula later). Let ''ℓ'' ≠ 0 be an integer. Since ''α'' is irrational, ''ℓα'' can never be an integer, so can never be 1. Using the formula for the sum of a finite ]geometric series
In mathematics, a geometric series is the sum of an infinite number of terms that have a constant ratio between successive terms. For example, the series
:\frac \,+\, \frac \,+\, \frac \,+\, \frac \,+\, \cdots
is geometric, because each su ...
,
:
a finite bound that does not depend on ''n''. Therefore, after dividing by ''n'' and letting ''n'' tend to infinity, the left hand side tends to zero, and Weyl's criterion is satisfied.
Conversely, notice that if ''α'' is rational
Rationality is the quality of being guided by or based on reasons. In this regard, a person acts rationally if they have a good reason for what they do or a belief is rational if it is based on strong evidence. This quality can apply to an abili ...
then this sequence is not equidistributed modulo 1, because there are only a finite number of options for the fractional part of ''a''''j'' = ''jα''.
Complete uniform distribution
A sequence of real numbers is said to be ''k-uniformly distributed mod 1'' if not only the sequence of fractional parts