Definitions
Nearby Words

# Equidistributed sequence

In mathematics, a bounded sequence {s1, s2, s3, …} of real numbers is said to be equidistributed, or uniformly distributed, if the proportion of terms falling in an subinterval is proportional to the length of that interval. Such sequences are studied in Diophantine approximation theory and have applications to Monte Carlo integration.

## Definition

A bounded sequence {s1, s2, s3, …} of real numbers is said to be equidistributed on an interval [ab] if for any subinterval [cd] of [ab] we have
$lim_\left\{ntoinfty\right\}\left\{ left|\left\{,s_1,dots,s_n ,\right\} cap \left[c,d\right] right| over n\right\}=\left\{d-c over b-a\right\} . ,$
(Here, the notation |{s1,…,sn }∩[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 [0, 2], since the interval [0.5, 0.9] occupies 1/5 of the length of the interval [0, 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 {sn} 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 {s1, s2, s3, …} with respect to the interval [ab] as

$D\left(N\right) = sup_\left\{ale cle dle b\right\} leftvert frac\left\{left|\left\{,s_1,dots,s_N ,\right\} cap \left[c,d\right] right|\right\}\left\{N\right\} - frac\left\{d-c\right\}\left\{b-a\right\} rightvert . ,$

A sequence is thus equidistributed if the discrepancy D(N) tends to zero as N tends to infinity.

### Equidistribution modulo 1

The sequence {a1, a2, a3, …} is said to be equidistributed modulo 1 or uniformly distributed modulo 1 if the sequence of the fractional parts of the an's, (denoted by an−⌊an⌋)

$\left\{ a_1-lfloor a_1rfloor, a_2-lfloor a_2rfloor, a_3-lfloor a_3rfloor, dots \right\}$

is equidistributed in the interval [0, 1].

## Examples

• The sequence of all multiples of an irrational α,

0, α, 2α, 3α, 4α, …
is uniformly distributed modulo 1: this is the equidistribution theorem.

• More generally, if p is a polynomial with at least one irrational coefficient (other than the constant term) then the sequence p(n) is uniformly distributed modulo 1: this is a theorem of Johannes van der Corput.
• The sequence log(n) is not uniformly distributed modulo 1.
• 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, proved by I. M. Vinogradov in 1935.

## Properties

The following three conditions are equivalent:

1. {an} is equidistributed modulo 1.
2. For every Riemann integrable function f on [0, 1],

$lim_\left\{ntoinfty\right\} frac\left\{1\right\}\left\{n\right\} sum_\left\{j=1\right\}^n f\left(a_j\right)=int_0^1 f\left(x\right), dx.$
1. For every nonzero integer k,
$lim_\left\{ntoinfty\right\} frac\left\{1\right\}\left\{n\right\} sum_\left\{j=1\right\}^n e^\left\{2pi ik a_j\right\}=0.$
The third condition is known as Weyl's criterion. Together with the formula for the sum of a finite geometric series, the equivalence of the first and third conditions furnishes an immediate proof of the equidistribution theorem.

## Metric theorems

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.

• For any sequence of distinct integers bn, the sequence {bn α} is equidistributed mod 1 for almost all values of α.
• The sequence {αn} is equidistributed mod 1 for almost all values of α.

It is not known whether the sequences {en} or {πn} are equidistributed mod 1. However it is known that the sequence {αn} is not equidistributed mod 1 if α is a PV number.

## Well-distributed sequence

A bounded sequence {s1, s2, s3, …} of real numbers is said to be well-distributed on [ab] if for any subinterval [cd] of [ab] we have
$lim_\left\{ntoinfty\right\}\left\{ left|\left\{,s_\left\{k+1\right\},dots,s_\left\{k+n\right\} ,\right\} cap \left[c,d\right] right| over n\right\}=\left\{d-c over b-a\right\} ,$

uniformly in k. Clearly every well-distributed sequence is uniformly distributed, but the converse does not hold. The definition of well-distributed modulo 1 is analogous.