<center> <img src = "https://i.imgsafe.org/96/96dff23960.png" /> </center>

# 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 <img src="http://latex.codecogs.com/gif.latex?\left\{&space;a_n&space;\right\}" title="\left\{ a_n \right\}" align = "center"/> is said to be __equidistributed__ on non degenerate interval <img src="http://latex.codecogs.com/gif.latex?[x,&space;y]" title="[x, y]" align = "center"/> if for any subinterval <img src="http://latex.codecogs.com/gif.latex?[\alpha,&space;\beta]&space;\subset&space;[x,&space;y]" title="[\alpha, \beta] \subset [x, y]" align = "center"/>, we have

<center> <img src="http://latex.codecogs.com/gif.latex?\lim_{N&space;\rightarrow&space;\infty}&space;\frac{\&hash;&space;\left\{&space;a_{n}&space;\in&space;[\alpha,&space;\beta]&space;:&space;1&space;\leq&space;n&space;\leq&space;N&space;\right\}}{N}&space;=&space;\frac{\beta&space;-&space;\alpha}{y&space;-&space;x}" title="\lim_{N \rightarrow \infty} \frac{\# \left\{ a_{n} \in [\alpha, \beta] : 1 \leq n \leq N \right\}}{N} = \frac{\beta - \alpha}{y - x}" /> </center> 

What it means is the following. 

Considering __more and more terms__ (<img src="http://latex.codecogs.com/gif.latex?N&space;\rightarrow&space;\infty" title="N \rightarrow \infty" />), the __ratio__ of the number of terms inside the subinterval <img src="http://latex.codecogs.com/gif.latex?[\alpha,&space;\beta]" title="[\alpha, \beta]" align = "center"/> to the total <img src="http://latex.codecogs.com/gif.latex?N" title="N" /> should __converge__ to the ratio of length of each subinterval vs total. 

---

The case when <img src="http://latex.codecogs.com/gif.latex?x&space;=&space;0,&space;y=&space;1" title="x = 0, y= 1" align=  "center"/> is of particular interest, since  <img src="http://latex.codecogs.com/gif.latex?[0,&space;1]" title="[0, 1]" align = "center"/> is the __unit interval__. Rewriting the definition, we can rewrite as follows. For  <img src="http://latex.codecogs.com/gif.latex?\left\{&space;\alpha_n&space;\right\}&space;\subset&space;[0,&space;1]" title="\left\{ \alpha_n \right\} \subset [0, 1]" align = "center"/> and <img src="http://latex.codecogs.com/gif.latex?[\alpha,&space;\beta]&space;\subset&space;[0,&space;1]," title="[\alpha, \beta] \subset [0, 1]," align=  "center"/> equidistribution is equivalent to 

<center> <img src="http://latex.codecogs.com/gif.latex?\lim_{N&space;\rightarrow&space;\infty}&space;\frac{\&hash;&space;\left\{&space;a_n&space;\in&space;[\alpha&space;,\beta]:&space;1&space;\leq&space;n&space;\leq&space;N&space;\right\}}{N}&space;=&space;\beta&space;-&space;\alpha" title="\lim_{N \rightarrow \infty} \frac{\# \left\{ a_n \in [\alpha ,\beta]: 1 \leq n \leq N \right\}}{N} = \beta - \alpha" /> </center> 

## 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__ 

<center> <img src="http://latex.codecogs.com/gif.latex?\alpha&space;\leq&space;a_n&space;\leq&space;\beta" title="\alpha \leq a_n \leq \beta" /> </center>

__for all__ <img src="http://latex.codecogs.com/gif.latex?N" title="N" /> (or at least prove the convergence directly).  


### 2-2. Weyl's Criterion - A Great Breakthrough
<center>
<img src = "https://i.imgsafe.org/96/96c8e44d0d.jpeg" height = "300" width = "300"/> </center>
[2] 

In 1916, on his paper [<___On the distribution of numbers modulo 1___>](http://www.fuchs-braun.com/media/3ed54b58b68a224cffff80dffffffff1.pdf) - [3], German Mathematician [Hermann Weyl](https://en.wikipedia.org/wiki/Hermann_Weyl) proved the following ingenious criterion for determination of equidistribution of particular sequence. 

---
#### Weyl's Criterion. -[4]
A sequence of real numbers <img src="http://latex.codecogs.com/gif.latex?\left\{&space;\xi_n&space;\right\}" title="\left\{ \xi_n \right\} \subset [0, 1]" align = "center"/>  is equidistributed modulo 1 __if and only if__ for all integers <img src="http://latex.codecogs.com/gif.latex?k&space;\neq&space;0" title="k \neq 0" align = "center"/>, we have 

<center> <img src="http://latex.codecogs.com/gif.latex?\lim_{N&space;\rightarrow&space;\infty}&space;\frac{1}{N}&space;\sum_{n=1}^{N}&space;e^{2\pi&space;i&space;k&space;\xi_n}&space;=&space;0" title="\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^{N} e^{2\pi i k \xi_n} = 0" /> </center>

where <img src="http://latex.codecogs.com/gif.latex?i&space;=&space;\sqrt{-1}" title="i = \sqrt{-1}" align = "center"/> is the imaginary number, and modulo 1 implies the fractional part, 

<center> <img src="http://latex.codecogs.com/gif.latex?\langle&space;\xi_n&space;\rangle&space;=&space;\xi_n&space;-&space;\lfloor&space;\xi_n&space;\rfloor" title="\langle \xi_n \rangle = \xi_n - \lfloor \xi_n \rfloor" /> </center>

---

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](https://warwick.ac.uk/fac/sci/maths/undergrad/ughandbook/resources/ma433/2014/weyl.pdf) - [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 <img src="http://latex.codecogs.com/gif.latex?a&space;\in&space;\mathbb{R}" title="a \in \mathbb{R}" /> , and construct a sequence <img src="http://latex.codecogs.com/gif.latex?\left\{&space;\langle&space;n&space;a&space;\rangle&space;\right\}" title="\left\{ \langle n a \rangle \right\}" align = "center"/> , where 

<center> <img src="http://latex.codecogs.com/gif.latex?\langle&space;na&space;\rangle&space;=&space;na&space;-&space;\lfloor&space;na&space;\rfloor" title="\langle na \rangle = na - \lfloor na \rfloor" /> </center>

denotes the fractional part of <img src="http://latex.codecogs.com/gif.latex?na" title="na" /> . Then using <img src="http://latex.codecogs.com/gif.latex?\xi_n&space;=&space;na" title="\xi_n = na" align = "center"/> , the criterion gives

<center> <img src="http://latex.codecogs.com/gif.latex?\begin{align*}&space;\left|&space;\sum_{n=1}^{N}&space;e^{2\pi&space;i&space;k&space;\xi_n}&space;\right|&space;&=&space;\left|&space;\sum_{n=1}^{N}&space;e^{2\pi&space;i&space;k&space;n&space;a}&space;\right|&space;\\&space;&=&space;\left|&space;\frac{e^{2\pi&space;i&space;k&space;a}&space;(&space;1&space;-&space;e^{2&space;\pi&space;i&space;N&space;a})}{1&space;-&space;e^{2&space;\pi&space;i&space;k&space;a}}&space;\right|\\&space;&\leq&space;\left|&space;\frac{&space;1&space;-&space;e^{2&space;\pi&space;i&space;N&space;a}}{1&space;-&space;e^{2&space;\pi&space;i&space;a}}&space;\right|&space;\leq&space;\frac{2}{\left|&space;1&space;-&space;e^{2&space;\pi&space;i&space;k&space;a}&space;\right|}&space;\end{align*}" title="\begin{align*} \left| \sum_{n=1}^{N} e^{2\pi i k \xi_n} \right| &= \left| \sum_{n=1}^{N} e^{2\pi i k n a} \right| \\ &= \left| \frac{e^{2\pi i k a} ( 1 - e^{2 \pi i N a})}{1 - e^{2 \pi i k a}} \right|\\ &\leq \left| \frac{ 1 - e^{2 \pi i N a}}{1 - e^{2 \pi i a}} \right| \leq \frac{2}{\left| 1 - e^{2 \pi i k a} \right|} \end{align*}" /> </center>

so that 
<center> <img src="http://latex.codecogs.com/gif.latex?\lim_{N&space;\rightarrow&space;\infty}&space;\frac{1}{N}&space;\sum_{n=1}^{N}&space;e^{2\pi&space;i&space;k&space;\xi_n}&space;=&space;0" title="\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^{N} e^{2\pi i k \xi_n} = 0" /> </center>

because <img src="http://latex.codecogs.com/gif.latex?|1&space;-&space;e^{2\pi&space;i&space;k&space;a}|&space;\neq&space;0" title="|1 - e^{2\pi i k a}| \neq 0" align = "center"/> (<img src="http://latex.codecogs.com/gif.latex?a" title="a" /> is irrational!) and independent of <img src="http://latex.codecogs.com/gif.latex?N" title="N" /> . 

So we've showed that <img src="http://latex.codecogs.com/gif.latex?\left\{&space;\langle&space;n&space;a&space;\rangle&space;\right\}" title="\left\{ \langle n a \rangle \right\}" align = "center"/> is equidistributed over  <img src="http://latex.codecogs.com/gif.latex?[0,&space;1]" title="[0, 1]" align = "center"/> for any irrational number <img src="http://latex.codecogs.com/gif.latex?a" title="a" /> . 

## 3. So where can we use this result?

Take <img src="http://latex.codecogs.com/gif.latex?a&space;=&space;\frac{1}{2\pi}" title="a = \frac{1}{2\pi}" align = "center"/> . Then, 

<center> <img src="http://latex.codecogs.com/gif.latex?\langle&space;na&space;\rangle&space;=&space;\langle&space;\frac{n}{2\pi}&space;\rangle&space;=&space;\frac{n}{2\pi}&space;-&space;\lfloor&space;\frac{n}{2\pi}&space;\rfloor" title="\langle na \rangle = \langle \frac{n}{2\pi} \rangle = \frac{n}{2\pi} - \lfloor \frac{n}{2\pi} \rfloor" /> </center> 

is equidistributed over <img src="http://latex.codecogs.com/gif.latex?[0,&space;1]" title="[0, 1]" align = "center" /> . Now consider the new sequence

<center> <img src="http://latex.codecogs.com/gif.latex?\psi_n&space;=&space;2\pi&space;\langle&space;n&space;a&space;\rangle&space;=&space;n&space;-&space;2\pi&space;\lfloor&space;\frac{n}{2\pi}&space;\rfloor" title="\psi_n = 2\pi \langle n a \rangle = n - 2\pi \lfloor \frac{n}{2\pi} \rfloor" /> </center>

This is nothing but <img src="http://latex.codecogs.com/gif.latex?n&space;\mod&space;2\pi" title="n \mod 2\pi" /> . Since it is just __scaling of the equidistributed sequence__, from  the definition, we can directly check the inequality holds for any subinterval of <img src="http://latex.codecogs.com/gif.latex?[0,&space;2\pi]" title="[0, 2\pi]" align = "center"/> .
Hmm, what function does come to your mind if you loot at <img src="http://latex.codecogs.com/gif.latex?2\pi" title="2\pi" /> ? YES! the <img src="http://latex.codecogs.com/gif.latex?\sin" title="\sin" /> fucntion! 

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

What is the actual distribution of <img src="http://latex.codecogs.com/gif.latex?\sin&space;n" title="\sin n" /> where <img src="http://latex.codecogs.com/gif.latex?n&space;=&space;1,&space;2,&space;...&space;\in&space;\mathbb{N}" title="n = 1, 2, ... \in \mathbb{N}" align = "center"/> ? Note that <img src="http://latex.codecogs.com/gif.latex?-1<&space;\sin&space;n&space;<1" title="-1< \sin n <1" align = "center"/> (it can not be -1 or 1). Here the distribution means the probability density function <img src="http://latex.codecogs.com/gif.latex?f(x)" title="f(x)" align = "center"/> over <img src="http://latex.codecogs.com/gif.latex?x&space;\in&space;(-1,&space;1)" title="x \in (-1, 1)" align = "center"/> such that 

<center> <img src="http://latex.codecogs.com/gif.latex?\int_{-1}^{1}&space;f(x)&space;dx&space;=&space;1" title="\int_{-1}^{1} f(x) dx = 1" /> </center>

So the first thing we should do is to find a continuous random variable <img src="http://latex.codecogs.com/gif.latex?X&space;\in&space;(-1,&space;1)" title="X \in (-1, 1)" align = "center"/> . Summarizing the observations made above,

1. <img src="http://latex.codecogs.com/gif.latex?n&space;\mod&space;2\pi" title="n \mod 2\pi" /> is equidistribution on <img src="http://latex.codecogs.com/gif.latex?[0,&space;2\pi]" title="[0, 2\pi]" align = "center"/>

2. <img src="http://latex.codecogs.com/gif.latex?\sin" title="\sin" /> has fundamental period <img src="http://latex.codecogs.com/gif.latex?2\pi" title="2\pi" /> . 

So distribution (in statistical sense) of <img src="http://latex.codecogs.com/gif.latex?\left\{&space;\sin&space;n&space;\right\}" title="\left\{ \sin n \right\}" align = "center"/> is equal to distribution of <img src="http://latex.codecogs.com/gif.latex?\sin&space;X" title="\sin X" /> where 

<center> <img src="http://latex.codecogs.com/gif.latex?X&space;\sim&space;Unif(-\pi/2,&space;\pi/2)" title="X \sim Unif(-1, 1)" align = "center" />
</center>

because <img src="http://latex.codecogs.com/gif.latex?\sin&space;X" title="\sin X" /> runs over <img src="http://latex.codecogs.com/gif.latex?(-1,&space;1)" title="(-1, 1)" align=  "center" /> and is invertible. Now if we denote PDF of <img src="http://latex.codecogs.com/gif.latex?\sin&space;X" title="\sin X" /> as <img src="http://latex.codecogs.com/gif.latex?g(x)" title="f(x)" align = "center"/> and PDF of <img src="http://latex.codecogs.com/gif.latex?X" title="X" /> as <img src="http://latex.codecogs.com/gif.latex?f(x)&space;=&space;1/2\pi" title="f(x) = 1/2" align = "center"/> (on interval <img src="http://latex.codecogs.com/gif.latex?(-1/2\pi,&space;1/2\pi)" title="(-1/2\pi, 1/2\pi)" align ="center"/> ), by transformation, 

<center> <img src="http://latex.codecogs.com/gif.latex?g(x)&space;=&space;\left|&space;\frac{d(\sin^{-1}x)}{dx}&space;\right|&space;f(\sin^{-1}(x))&space;=&space;\frac{1}{\pi&space;\sqrt{1-x^2}}&space;\&space;(x&space;\in&space;(-1,&space;1))" title="g(x) = \left| \frac{d(\sin^{-1}x)}{dx} \right| f(\sin^{-1}(x)) = \frac{1}{\pi \sqrt{1-x^2}} \ (x \in (-1, 1))" /> </center>

## 3-2. Visualization of the Result. 
Here is the MATLAB code for generating histogram of <img src="http://latex.codecogs.com/gif.latex?\sin&space;n" title="\sin n" /> where <img src="http://latex.codecogs.com/gif.latex?1&space;\leq&space;n&space;\leq&space;N" title="1 \leq n \leq N" align = "center"/> . 

```
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
<center> <img src= "https://i.imgsafe.org/96/9682a551d6.png" /> </center>

2. N = 100000
<center> <img src = "https://i.imgsafe.org/96/9682a54f81.png" /> </center>

3. N = 1000000
<center> <img src = "https://i.imgsafe.org/96/9682ee0792.png" /> </center>

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);
```
<center> <img src = "https://i.imgsafe.org/96/9691f4ebac.png" /> </center>

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](https://steemit.com/math/@mathsolver/math-talk-3-pigeonhole-principle-and-its-usage) that 

<center> <img src="http://latex.codecogs.com/gif.latex?\left\{&space;m&space;&plus;&space;na:&space;n,m&space;\in&space;\mathbb{Z}&space;\right\}" title="\left\{ m + na: n,m \in \mathbb{Z} \right\}" /> </center>

is dense in <img src="http://latex.codecogs.com/gif.latex?\mathbb{R}" title="\mathbb{R}" /> for any irrational number <img src="http://latex.codecogs.com/gif.latex?a" title="a" /> . We can easily extend this result to show that <img src="http://latex.codecogs.com/gif.latex?\left\{&space;\sin&space;n&space;\right\}" title="\left\{ \sin n \right\}" align = "center"/> is __dense subset of__ <img src="http://latex.codecogs.com/gif.latex?[-1,&space;1]" title="[-1, 1]" align = "center"/> . Even if it is dense, the distribution is not uniform! There are far more values concentrated close to __extreme left and right__; <img src="http://latex.codecogs.com/gif.latex?-1,&space;1" title="-1, 1" align = "center" />. 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 <img src="http://latex.codecogs.com/gif.latex?\sin&space;n" title="\sin n" /> 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.__