- Source: 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.
Definition
A sequence (s1, s2, s3, ...) 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
lim
n
→
∞
|
{
s
1
,
…
,
s
n
}
∩
[
c
,
d
]
|
n
=
d
−
c
b
−
a
.
{\displaystyle \lim _{n\to \infty }{\left|\{\,s_{1},\dots ,s_{n}\,\}\cap [c,d]\right| \over n}={d-c \over b-a}.}
(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 DN for a sequence (s1, s2, s3, ...) with respect to the interval [a, b] as
D
N
=
sup
a
≤
c
≤
d
≤
b
|
|
{
s
1
,
…
,
s
N
}
∩
[
c
,
d
]
|
N
−
d
−
c
b
−
a
|
.
{\displaystyle D_{N}=\sup _{a\leq c\leq d\leq b}\left\vert {\frac {\left|\{\,s_{1},\dots ,s_{N}\,\}\cap [c,d]\right|}{N}}-{\frac {d-c}{b-a}}\right\vert .}
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 ε. 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 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. 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 (s1, s2, s3, ...) 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) function f : [a, b] →
C
{\displaystyle \mathbb {C} }
, the following limit holds:
lim
N
→
∞
1
N
∑
n
=
1
N
f
(
s
n
)
=
1
b
−
a
∫
a
b
f
(
x
)
d
x
{\displaystyle \lim _{N\to \infty }{\frac {1}{N}}\sum _{n=1}^{N}f\left(s_{n}\right)={\frac {1}{b-a}}\int _{a}^{b}f(x)\,dx}
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 is considered and f is taken to be in L1, 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, so f is zero almost everywhere.
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 (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].
= Examples
=The equidistribution theorem: The sequence of all multiples of an irrational α,
0, α, 2α, 3α, 4α, ...
is equidistributed modulo 1.
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.
The sequence log(n) is not uniformly distributed modulo 1. This fact is related to Benford's law.
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, published by I. M. Vinogradov in 1948.
The van der Corput sequence is equidistributed.
= Weyl's criterion
=Weyl's criterion states that the sequence an is equidistributed modulo 1 if and only if for all non-zero integers ℓ,
lim
n
→
∞
1
n
∑
j
=
1
n
e
2
π
i
ℓ
a
j
=
0.
{\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{j=1}^{n}e^{2\pi i\ell a_{j}}=0.}
The criterion is named after, and was first formulated by, Hermann Weyl. It allows equidistribution questions to be reduced to bounds on exponential sums, 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 vn of vectors in Rk is equidistributed modulo 1 if and only if for any non-zero vector ℓ ∈ Zk,
lim
n
→
∞
1
n
∑
j
=
0
n
−
1
e
2
π
i
ℓ
⋅
v
j
=
0.
{\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{j=0}^{n-1}e^{2\pi i\ell \cdot v_{j}}=0.}
Example of usage
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.
Suppose α is irrational and denote our sequence by aj = 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
e
2
π
i
ℓ
α
{\textstyle e^{2\pi i\ell \alpha }}
can never be 1. Using the formula for the sum of a finite geometric series,
|
∑
j
=
0
n
−
1
e
2
π
i
ℓ
j
α
|
=
|
∑
j
=
0
n
−
1
(
e
2
π
i
ℓ
α
)
j
|
=
|
1
−
e
2
π
i
ℓ
n
α
1
−
e
2
π
i
ℓ
α
|
≤
2
|
1
−
e
2
π
i
ℓ
α
|
,
{\displaystyle \left|\sum _{j=0}^{n-1}e^{2\pi i\ell j\alpha }\right|=\left|\sum _{j=0}^{n-1}\left(e^{2\pi i\ell \alpha }\right)^{j}\right|=\left|{\frac {1-e^{2\pi i\ell n\alpha }}{1-e^{2\pi i\ell \alpha }}}\right|\leq {\frac {2}{\left|1-e^{2\pi i\ell \alpha }\right|}},}
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α.
= Complete uniform distribution
=A sequence
(
a
1
,
a
2
,
…
)
{\displaystyle (a_{1},a_{2},\dots )}
of real numbers is said to be k-uniformly distributed mod 1 if not only the sequence of fractional parts
a
n
′
:=
a
n
−
[
a
n
]
{\displaystyle a_{n}':=a_{n}-[a_{n}]}
is uniformly distributed in
[
0
,
1
]
{\displaystyle [0,1]}
but also the sequence
(
b
1
,
b
2
,
…
)
{\displaystyle (b_{1},b_{2},\dots )}
, where
b
n
{\displaystyle b_{n}}
is defined as
b
n
:=
(
a
n
+
1
′
,
…
,
a
n
+
k
′
)
∈
[
0
,
1
]
k
{\displaystyle b_{n}:=(a'_{n+1},\dots ,a'_{n+k})\in [0,1]^{k}}
, is uniformly distributed in
[
0
,
1
]
k
{\displaystyle [0,1]^{k}}
.
A sequence
(
a
1
,
a
2
,
…
)
{\displaystyle (a_{1},a_{2},\dots )}
of real numbers is said to be completely uniformly distributed mod 1 it is
k
{\displaystyle k}
-uniformly distributed for each natural number
k
≥
1
{\displaystyle k\geq 1}
.
For example, the sequence
(
α
,
2
α
,
…
)
{\displaystyle (\alpha ,2\alpha ,\dots )}
is uniformly distributed mod 1 (or 1-uniformly distributed) for any irrational number
α
{\displaystyle \alpha }
, but is never even 2-uniformly distributed. In contrast, the sequence
(
α
,
α
2
,
α
3
,
…
)
{\displaystyle (\alpha ,\alpha ^{2},\alpha ^{3},\dots )}
is completely uniformly distributed for almost all
α
>
1
{\displaystyle \alpha >1}
(i.e., for all
α
{\displaystyle \alpha }
except for a set of measure 0).
= van der Corput's difference theorem
=A theorem of Johannes van der Corput states that if for each h the sequence sn+h − sn is uniformly distributed modulo 1, then so is sn.
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.
= 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 α > 1.
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 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
lim
n
→
∞
|
{
s
k
+
1
,
…
,
s
k
+
n
}
∩
[
c
,
d
]
|
n
=
d
−
c
b
−
a
{\displaystyle \lim _{n\to \infty }{\left|\{\,s_{k+1},\dots ,s_{k+n}\,\}\cap [c,d]\right| \over n}={d-c \over b-a}}
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.
Sequences equidistributed with respect to an arbitrary measure
For an arbitrary probability measure space
(
X
,
μ
)
{\displaystyle (X,\mu )}
, a sequence of points
(
x
n
)
{\displaystyle (x_{n})}
is said to be equidistributed with respect to
μ
{\displaystyle \mu }
if the mean of point measures converges weakly to
μ
{\displaystyle \mu }
:
∑
k
=
1
n
δ
x
k
n
⇒
μ
.
{\displaystyle {\frac {\sum _{k=1}^{n}\delta _{x_{k}}}{n}}\Rightarrow \mu \ .}
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.
See also
Equidistribution theorem
Low-discrepancy sequence
Erdős–Turán inequality
Notes
References
Kuipers, L.; Niederreiter, H. (2006) [1974]. Uniform Distribution of Sequences. Dover Publications. ISBN 0-486-45019-8.
Kuipers, L.; Niederreiter, H. (1974). Uniform Distribution of Sequences. John Wiley & Sons Inc. ISBN 0-471-51045-9. Zbl 0281.10001.
Montgomery, Hugh L. (1994). Ten lectures on the interface between analytic number theory and harmonic analysis. Regional Conference Series in Mathematics. Vol. 84. Providence, RI: American Mathematical Society. ISBN 0-8218-0737-4. Zbl 0814.11001.
Further reading
Granville, Andrew; Rudnick, Zeév, eds. (2007). Equidistribution in number theory, an introduction. Proceedings of the NATO Advanced Study Institute on equidistribution in number theory, Montréal, Canada, July 11–22, 2005. NATO Science Series II: Mathematics, Physics and Chemistry. Vol. 237. Dordrecht: Springer-Verlag. ISBN 978-1-4020-5403-7. Zbl 1121.11004.
Tao, Terence (2012). Higher order Fourier analysis. Graduate Studies in Mathematics. Vol. 142. Providence, RI: American Mathematical Society. ISBN 978-0-8218-8986-2. Zbl 1277.11010.
External links
Weisstein, Eric W. "Equidistributed Sequence". MathWorld.
Weisstein, Eric W. "Weyl's Criterion". MathWorld.
Weyl's Criterion at PlanetMath.
Lecture notes by Charles Walkden with proof of Weyl's Criterion
Kata Kunci Pencarian:
- Equidistributed sequence
- Low-discrepancy sequence
- Normal number
- Uniform distribution
- Fractional part
- Weyl sequence
- Natural density
- Pseudorandom number generator
- Xorshift
- Mersenne Twister
