en>Wtmitchell: Reverted edits by 119.93.175.175 (talk) (HG)

2014-08-28T04:46:48Z

Reverted edits by 119.93.175.175 (talk) (HG)

en>ChrisGualtieri: Remove stub template(s). Page is start class or higher. Also check for and do General Fixes + Checkwiki fixes using AWB

2013-12-12T20:33:36Z

Remove stub template(s). Page is start class or higher. Also check for and do General Fixes + Checkwiki fixes using AWB

New page

In [[mathematics]], a bounded sequence {''s''1, ''s''2, ''s''3, …} of [[real number]]s is said to be '''equidistributed''', or '''uniformly distributed''', if the proportion of terms falling in a 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 {''s''1, ''s''2, ''s''3, …} of [[real number]]s is said to be ''equidistributed'' on an interval [''a'', ''b''] if for any subinterval [''c'', ''d''] of [''a'', ''b''] we have
:<math>\lim_{n\to\infty}{ \left|\{\,s_1,\dots,s_n \,\} \cap [c,d] \right| \over n}={d-c \over b-a} . \,</math>
(Here, the notation |{''s''1,…,''s''''n'' }∩[''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 {''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

:<math> D(N) = \sup_{a\le c\le d\le b} \left\vert \frac{\left|\{\,s_1,\dots,s_N \,\} \cap [c,d] \right|}{N} - \frac{d-c}{b-a} \right\vert . \,</math>

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 ε. See [[low-discrepancy sequence]] for stronger criteria and [[constructions of low-discrepancy sequences]] for constructions of sequences which are more evenly distributed.

===Equidistribution modulo 1===
The sequence {''a''1, ''a''2, ''a''3, …} is said to be '''equidistributed modulo 1''' or '''uniformly distributed modulo 1''' if the sequence of the [[fractional part]]s of the ''a''''n'''s, (denoted by ''a''''n''−&lfloor;''a''''n''&rfloor;)

:<math> \{ a_1-\lfloor a_1\rfloor, a_2-\lfloor a_2\rfloor, a_3-\lfloor a_3\rfloor, \dots \} </math>

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:<ref name=KN8>Kuipers & Niederreiter (2006) p. 8</ref> 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 was proven by Weyl and is an application of van der Corput's difference theorem.<ref name=KN27>Kuipers & Niederreiter (2006) p. 27</ref>
* The sequence log(''n'') is ''not'' uniformly distributed modulo 1.<ref name=KN8/>
* The sequence of all multiples of an irrational α by successive [[prime number]]s,
::2α, 3α, 5α, 7α, 11α, …
is equidistributed modulo 1. This is a famous [[theorem]] of [[analytic number theory]], proven by [[I. M. Vinogradov]] in 1935.
* The [[van der Corput sequence]] is equidistributed.<ref name=KN127>Kuipers & Niederreiter (2006) p. 127</ref>

==van der Corput's difference theorem==
A theorem of [[Johannes van der Corput]]<ref>{{Citation | last=van der Corput | first=J. | authorlink=Johannes van der Corput | title=Diophantische Ungleichungen. I. Zur Gleichverteilung Modulo Eins | publisher=Springer Netherlands | year=1931 | journal=[[Acta Mathematica]] | issn=0001-5962 | volume=56 | pages=373–456 | doi=10.1007/BF02545780 | zbl=0001.20102 | jfm=57.0230.05 }}</ref> states that if for each ''h'' the sequence ''s''''n''+''h''−s''n'' is uniformly distributed modulo 1, then so is s''n''.<ref>Kuipers & Niederreiter (2006) p. 26</ref><ref name=Mon18>Montgomery (1994) p.18</ref>

A '''van der Corput set''' is a set ''H'' of integers such that if for each ''h'' in ''H'' the sequence ''s''''n''+''h''−s''n'' is uniformly distributed modulo 1, then so is s''n''.<ref name=Mon18/>

==Properties==
The following three conditions are equivalent:
# {''a''''n''} is equidistributed modulo 1.
# For every Riemann integrable function ''f'' on [0, 1],
::<math>\lim_{n\to\infty} \frac{1}{n} \sum_{j=1}^n f(a_j)=\int_0^1 f(x)\, dx.</math>
<ol start=3><li>For every nonzero integer ''k'',
::<math>\lim_{n\to\infty} \frac{1}{n} \sum_{j=1}^n e^{2\pi ik a_j}=0.</math>
</ol>
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 ''b''''n'', the sequence {''b''''n'' α} is equidistributed mod 1 for almost all values of α.<ref>See {{citation | title=Über eine Anwendung der Mengenlehre auf ein aus der Theorie der säkularen Störungen herrührendes Problem | first=Felix | last=Bernstein | authorlink=Felix Bernstein | journal=[[Mathematische Annalen]] | volume=71 | number=3 | year=1911 | pages=417–439 | doi=10.1007/BF01456856 }}.</ref>
* The sequence {α''n''} is equidistributed mod 1 for almost all values of α > 1.<ref>{{citation | url=http://www.numdam.org/item?id=CM_1935__2__250_0 | title=Ein mengentheoretischer Satz über die Gleichverteilung modulo Eins | first=J. F. | last=Koksma | authorlink=Jurjen Ferdinand Koksma | journal=[[Compositio Mathematica]] | volume=2 | year=1935 | pages=250–258 | zbl=0012.01401 | jfm=61.0205.01 }}</ref>
It is not known whether the sequences {e''n''} 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 {''s''1, ''s''2, ''s''3, …} of [[real number]]s is said to be '''well-distributed''' on [''a'', ''b''] if for any subinterval [''c'', ''d''] of [''a'', ''b''] we have
:<math>\lim_{n\to\infty}{ \left|\{\,s_{k+1},\dots,s_{k+n} \,\} \cap [c,d] \right| \over n}={d-c \over b-a} \,</math>

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]] <math>(X,\mu)</math>, a sequence of points <math>x_n</math> is said to be equidistributed with respect to <math>\mu</math> if the mean of [[Dirac delta function|point measures]] [[Convergence_of_measures#Weak_convergence_of_measures|converges weakly]] to <math>\mu</math>:
:<math>\frac{\sum_{k=1}^n \delta_{x_k}}{n}\Rightarrow \mu</math>
It is true, for example. that for any probabilistic [[borel measure]] on a [[separable space|separable]], [[metrizable]] space, there exists an equidistributed sequence (with respect to the measure).

== See also ==
*[[Equidistribution theorem]]
*[[Low-discrepancy sequence]]

== References ==
{{reflist}}
* {{cite book | first1=L. | last1=Kuipers | first2=H. | last2=Niederreiter | title=Uniform Distribution of Sequences | publisher=Dover Publishing | year=2006 | isbn=0-486-45019-8 }}
* {{cite book | first1=L. | last1=Kuipers | first2=H. | last2=Niederreiter | title=Uniform Distribution of Sequences | publisher=John Wiley & Sons Inc. | year=1974 | isbn=0-471-51045-9 }}
* {{cite book | last=Montgomery | first=Hugh L. | authorlink=Hugh Montgomery (mathematician) | title=Ten lectures on the interface between analytic number theory and harmonic analysis | series=Regional Conference Series in Mathematics | volume=84 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=1994 | isbn=0-8218-0737-4 | zbl=0814.11001 }}

==Further reading==
* {{cite book | zbl=pre06110460 | last=Tao | first=Terence | authorlink=Terence Tao | title=Higher order Fourier analysis | series=Graduate Studies in Mathematics | volume=142 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2012 | isbn=978-0-8218-8986-2 | url=http://terrytao.wordpress.com/books/higher-order-fourier-analysis/ }}

==External links==
* {{MathWorld|title=Equidistributed Sequence|urlname=EquidistributedSequence}}

[[Category:Diophantine approximation]]
[[Category:Ergodic theory]]

Solar zenith angle - Revision history

en>Wtmitchell: Reverted edits by 119.93.175.175 (talk) (HG)

en>ChrisGualtieri: Remove stub template(s). Page is start class or higher. Also check for and do General Fixes + Checkwiki fixes using AWB