Distribution of Sequence - Weird Results

1. What is Equidistribution?

From statistics, distribution is nothing but a probability mass function (for discrete random variables) or probability density function (for continuous random variables). For sequences, we use the following defnition.

---

Definition. - [1]

A sequence is said to be equidistributed on non degenerate interval if for any subinterval , we have

What it means is the following.

Considering more and more terms (), the ratio of the number of terms inside the subinterval to the total should converge to the ratio of length of each subinterval vs total.

---

The case when is of particular interest, since is the unit interval. Rewriting the definition, we can rewrite as follows. For and equidistribution is equivalent to

2. Weyl's Criterion

2-1. What is the problem?

The definition is self-clear and intuitive. The proportion of terms inside the given subinterval should converge to subinterval's length as we consider more and more terms. However, the problem is that

Even if we are given a specific sequence (or furthermore closed form expression), it is hard to analytically solve the equality

for all (or at least prove the convergence directly).

2-2. Weyl's Criterion - A Great Breakthrough

[2]

In 1916, on his paper <On the distribution of numbers modulo 1> - [3], German Mathematician Hermann Weyl proved the following ingenious criterion for determination of equidistribution of particular sequence.

---

Weyl's Criterion. -[4]

A sequence of real numbers is equidistributed modulo 1 if and only if for all integers , we have

where is the imaginary number, and modulo 1 implies the fractional part,

---

The proof is not difficult (only uses elementary analysis including Riemann integrals), but lengthy enough (including some propositions and corollaries to be stated), so I will just post a link - [5]. (Believe me it's not hard). What's important of this criterion is the following fact that we are gonna use.

2-3. Irrational numbers and Equidistribution - [6]

Pick any irrational number , and construct a sequence , where

denotes the fractional part of . Then using , the criterion gives

so that

because ( is irrational!) and independent of .

So we've showed that is equidistributed over for any irrational number .

3. So where can we use this result?

Take . Then,

is equidistributed over . Now consider the new sequence

This is nothing but . Since it is just scaling of the equidistributed sequence, from the definition, we can directly check the inequality holds for any subinterval of .
Hmm, what function does come to your mind if you loot at ? YES! the fucntion!

3-1. Distribution of sin(n) - [6]

What is the actual distribution of where ? Note that (it can not be -1 or 1). Here the distribution means the probability density function over such that

So the first thing we should do is to find a continuous random variable . Summarizing the observations made above,

1. is equidistribution on

2. has fundamental period .

So distribution (in statistical sense) of is equal to distribution of where

because runs over and is invertible. Now if we denote PDF of as and PDF of as (on interval ), by transformation,

3-2. Visualization of the Result.

Here is the MATLAB code for generating histogram of where .

N = [10^4 10^5 10^6];  % Number of iteration
%-------------------------------------------------------%
for i = 1 : 1 : length(N)
    a = 1 : 1 : N(i);
    b = sin(a);
    figure;
    histogram(b); % Create histogram
end

1. N = 10000
   

   

2. N = 100000
   

   

3. N = 1000000
   

   

and the Probability density function we've obtained analytically

x = -1 : 0.01 : 1;
y = zeros(length(x));
for i = 1 : 1 : length(x);
    y(i) = 1/ (pi * sqrt(1-x(i)^2));
end
plot(x,y);

It perfectly matches~!

3-3. Some Important Facts to denote

There is a well known fact (and we've proved it on the previous section using pigeonhole principle that

is dense in for any irrational number . We can easily extend this result to show that is dense subset of . Even if it is dense, the distribution is not uniform! There are far more values concentrated close to extreme left and right; . So this shows that

Elements in countable dense subset of closed interval do not need to be equidistributed!

4. Conclusion

From the distribution of a sequence, we actually computed the distribution function of viewed as a continuous sense.

5. Citations

[1] https://warwick.ac.uk/fac/sci/maths/undergrad/ughandbook/resources/ma433/2014/weyl.pdf

[2] https://en.wikipedia.org/wiki/Hermann_Weyl (image is used)

[3] http://www.fuchs-braun.com/media/3ed54b58b68a224cffff80dffffffff1.pdf

[4] http://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf , page 7

[5] http://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf , page 1 through 7

[6] http://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf , page 8 Example 2.1 and page 23 Exercise 2.7

All the graphs and distributions are made by myself using MATLAB.