Equidistributed sequence

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 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.

Contents

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_{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 D(N) for a sequence {s1, s2, s3, …} with respect to the interval [ab] as

 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 . \,

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 {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⌋)

 \{ a_1-\lfloor a_1\rfloor, a_2-\lfloor a_2\rfloor, a_3-\lfloor a_3\rfloor, \dots \}

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 was proved by Weyl and is an application of the 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_{n\to\infty} \frac{1}{n} \sum_{j=1}^n f(a_j)=\int_0^1 f(x)\, dx.
  1. For every nonzero integer k,
    \lim_{n\to\infty} \frac{1}{n} \sum_{j=1}^n e^{2\pi ik a_j}=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 α.[1]
  • The sequence {αn} is equidistributed mod 1 for almost all values of α > 1.[2]

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_{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.

See also

References

  1. ^ See Satz 1, Über eine Anwendung der Mengenlehre auf ein aus der Theorie der säkularen Störungen herrührendes Problem, Felix Bernstein, Mathematische Annalen 71, #3 (September 1911), pp. 417-439, doi:10.1007/BF01456856.
  2. ^ Ein mengentheoretischer Satz über die Gleichverteilung modulo Eins, J. F. Koksma, Compositio Mathematica, 2 (1935), pp. 250-258.
  • L. Kuipers; H. Niederreiter (2006). Uniform Distribution of Sequences. Dover Publishing. ISBN 0-486-45019-8. 
  • L. Kuipers; H. Niederreiter (1974). Uniform Distribution of Sequences. John Wiley & Sons Inc.. ISBN 0-471-51045-9. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • Monte Carlo integration — An illustration of Monte Carlo integration. In this example, the domain D is the inner circle and the domain E is the square. Because the square s area can be easily calculated, the area of the circle can be estimated by the ratio (0.8) of the… …   Wikipedia

  • Natural density — In number theory, asymptotic density (or natural density or arithmetic density) is one of the possibilities to measure how large a subset of the set of natural numbers is. Intuitively, we think that there are more positive integers than perfect… …   Wikipedia

  • Uniform distribution — can refer to:Probability theory* discrete uniform distribution * continuous uniform distributionThey share the property that they have a finite range, and are weakly unimodal where any members of their support can be taken to be the mode. In… …   Wikipedia

  • Fractional part — All real numbers can be written in the form n + r where n is an integer (the integer part) and the remaining fractional part r is a nonnegative real number less than one. For a positive number written in decimal notation, the fractional part… …   Wikipedia

  • Normal number — For the floating point meaning in computing, see normal number (computing). In mathematics, a normal number is a real number whose infinite sequence of digits in every base b[1] is distributed uniformly in the sense that each of the b digit… …   Wikipedia

  • Mersenne twister — The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞?) and Takuji Nishimura (西村 拓士?)[1] …   Wikipedia

  • Weyl's criterion — In mathematics, in the theory of diophantine approximation, Weyl s criterion states that a sequence (x {n}) of real numbers is equidistributed mod 1 if and only if for all non zero integers ell we have::lim {n ightarrowinfty}frac{1}{n}sum… …   Wikipedia

  • Limit superior and limit inferior — In mathematics, the limit inferior (also called infimum limit, liminf, inferior limit, lower limit, or inner limit) and limit superior (also called supremum limit, limsup, superior limit, upper limit, or outer limit) of a sequence can be thought… …   Wikipedia

  • Pseudorandom number generator — A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG),[1] is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”