Equidistributed sequence
In mathematics, a sequence (s1, s2, s3, ...) 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.
Loosely speaking, one could say that each member of the sequence is equally likely to fall anywhere in its range.
We define the discrepancy DN for a sequence (s1, s2, s3, ...) with respect to the interval [a, b] as A sequence is thus equidistributed if the discrepancy DN 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 ε.
Recall that if f is a function having a Riemann integral in the interval [a, b], then its integral is the limit of Riemann sums taken by sampling the function f in a set of points chosen from a fine partition of the interval.
Note that both sides of the integral criterion equation are linear in f, and therefore the criterion holds for linear combinations of interval indicators, that is, step functions.
To show it holds for f being a general Riemann-integrable function, first assume f is real-valued.
Then by using Darboux's definition of the integral, we have for every ε > 0 two step functions f1 and f2 such that f1 ≤ f ≤ f2 and
∎ 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.
[2] A sequence (a1, a2, a3, ...) of real numbers is said to be equidistributed modulo 1 or uniformly distributed modulo 1 if the sequence of the fractional parts of an, denoted by (an) or by an − ⌊an⌋, is equidistributed in the interval [0, 1].
This was proven by Weyl and is an application of van der Corput's difference theorem.
[4] Weyl's criterion states that the sequence an 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.
[7] It allows equidistribution questions to be reduced to bounds on exponential sums, a fundamental and general method.
It is possible to bound f from above and below by two continuous functions on the interval, whose integrals differ by an arbitrary ε.
By an argument similar to the proof of the Riemann integral criterion, it is possible to extend the result to any interval indicator function f, thereby proving equidistribution modulo 1 of the given sequence.
∎ The sequence vn of vectors in Rk is equidistributed modulo 1 if and only if for any non-zero vector ℓ ∈ Zk, Weyl's criterion can be used to easily prove the equidistribution theorem, stating that the sequence of multiples 0, α, 2α, 3α, ... of some real number α is equidistributed modulo 1 if and only if α is irrational.
[3] Suppose α is irrational and denote our sequence by aj = jα (where j starts from 0, to simplify the formula later).
Using the formula for the sum of a finite geometric series, 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 then this sequence is not equidistributed modulo 1, because there are only a finite number of options for the fractional part of aj = jα.
of real numbers is said to be k-uniformly distributed mod 1 if not only the sequence of fractional parts
of real numbers is said to be completely uniformly distributed mod 1 it is
[9][10][11] A van der Corput set is a set H of integers such that if for each h in H the sequence sn+h − sn is uniformly distributed modulo 1, then so is sn.
[10][11] Metric theorems describe the behaviour of a parametrised sequence for almost all values of some parameter α: that is, for values of α not lying in some exceptional set of Lebesgue measure zero.
However it is known that the sequence (αn) is not equidistributed mod 1 if α is a PV number.
A sequence (s1, s2, s3, ...) of real numbers is said to be well-distributed on [a, b] if for any subinterval [c, d ] of [a, b] we have uniformly in k. Clearly every well-distributed sequence is uniformly distributed, but the converse does not hold.
:[14] In any Borel probability measure on a separable, metrizable space, there exists an equidistributed sequence with respect to the measure; indeed, this follows immediately from the fact that such a space is standard.
The general phenomenon of equidistribution comes up a lot for dynamical systems associated with Lie groups, for example in Margulis' solution to the Oppenheim conjecture.
