Golden ratio mod 1 distribution

If you plot the sequence

x(x+φ) mod 1

you get a nice scattering of numbers where no number is close to any previous number. This image shows the sequence after each iteration. You can (sort of) see that at every column the horizontal lines are roughly evenly distributed. Edit: To be clear I mean even the very first iterations make nicely evenly distributed numbers, which not all rational numbers do. φ is special in some way.

To put it a better way, with φ the distance from the last number in the sequence to the nearest number is always close to as high as possible. It never puts a number close to an existing one unless necessary.


Why does this happen, and is there an equivalent process for two or three dimensions?


Part 1.

As mentioned in the comments, the equidistribution theorem, states that in the limit any irrational value will produce an equidistributed sequence. That is, in the limit as n \rightarrow \infty, all values of x are equally likely, and thus it is said that the range of the sequence is dense on the interval [0,1]. This was proven by Weyl, and so this theorem is often called Weyl’s criterion.

However, as you have mentioned, equidistribution is quite a weak criterion and does not necessarily imply that for finite n the sequence will fill the interval ‘evenly’ without large gaps or clusters.

Sequences that satisfy this stronger criterion of ‘evenness’ are called low discrepancy sequences.

There are many ways to construct low discrepancy sequences, including the van der Corput / Halton sequences, Niederreiter and Sobol sequences to name a few. However, by far the most simple to construct are the Kronecker (sometimes called Weyl) additive recurrence sequences, which are defined exactly as you describe in your question. That is,
x_n = \alpha_0 + \alpha n \; (\textrm{mod} \; 1), \quad n=1,2,3,…
The choice of \alpha_0 does not affect the underlying characteristics of the sequence and so for reasons of simplicty is usually set to zero. (However, for reasons associated with symmetry \alpha_0 = 1/2 is possibly preferable.)

It turns out that only certain values of \alpha produce low discrepancy sequences. For number theoretic reasons, these special values of \alpha are also correspond to numbers that are badly approximable (by the rationals). Intuitively one can say that the more badly approximable a number is by the rationals, the ‘more irrational’ it is. This is why the golden ratio, which is the most badly approximable number, is often described as the most irrational number. The more irrational the value of \alpha is, the better (‘more even’) the low discrepancy sequence will be. Thus, the golden ratio \varphi = \frac{1+\sqrt{5}}{2} produces the optimal low discrepancy sequence.

Two lesser known facts are worth mentioning.

Firstly, any value of \alpha related via the transformation,
\alpha = \frac{a+b\varphi}{c+d\varphi} \quad \textrm{for integers} \;\;a,b,c,d \;\; \textrm{where} \; |ad-bc|=1.
will also be optimal.

And secondly, \alpha = 1+\sqrt{2} turns out to be the next most badly approximable number — and therefore the next most optimal value for the construction of a low discrepancy sequence. Springborn as well as Spalding give number theoretic reasons why this is the second most badly approximable number

Furthermore, using this same line of argument, they explains why \alpha = \frac{1}{10} (9+\sqrt{221}) is the third-most badly approximable number.

Interestingly the continued fraction for these three values are:
\varphi = 1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+…}}} = [1;1,1,1,…]
1+\sqrt{2} = 2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+…}}} = [2;2,2,2,2,2]
\frac{1}{10}(9+\sqrt{221}) = 2+\cfrac{1}{2+\cfrac{1}{1+\cfrac{1}{1+…}}} = [2;2,1,1,2,2,1,1,2,2,1,1,..]

Part 2

Regarding the final part of your question as to if there is an equivalent process for higher dimensions, the answer is a resounding ‘Yes!‘.

Here are some different two dimensional low discrepancy sequences.
enter image description here

I give details, including many explanatory pictures, of this in my blog post, ‘The unreasonable effectiveness of quasirandom sequences‘, but the short version is as follows:

The sequence of d-dimensional vectors \pmb{x}_n \in U[0,1]^d (for a given constant \pmb{\alpha} = (\alpha_1, \alpha_2,…,\alpha_d), defined as follows:

\pmb{x}_n = \pmb{\alpha}_0 + n\pmb{\alpha} \; (\textrm{mod} \; 1), \quad n=1,2,3,…

is equidistributed if \alpha_i are all independently irrational numbers.

In most applications, the construction of such a d-dimensional low discrepancy sequence is based on the square roots of the first d prime numbers. That is, \pmb{\alpha} = (\sqrt{2}, \sqrt{3}, \sqrt{5},..)

This produces quite good results. However, significantly better results can be achieved by creating a recurrence sequence based on a value \varphi_d that is a d-dimensional generalisation fo the golden ratio, \varphi.

\pmb{\varphi} =(\frac{1}{\varphi_d}, \frac{1}{\varphi_d^2},\frac{1}{\varphi_d^3},…\frac{1}{\varphi_d^d}),

\textrm{where} \; \varphi_d\ \textrm{is the unique positive root of } x^{d+1}=x+1.

Note that in the 1-dimensional case, this results in \varphi_1 = \varphi, the canonical golden ratio.

In the two dimensional case, \varphi_2 corresponds to what is often called the plastic constant. A beautiful dynamic visualization of the low discrepancy sequence based on this plastic constant can be found here.

A dynamic comparison of the different 2-dimensional low discrepancy sequences as n increases, is shown below.

enter image description here

Hope this helps!

Source : Link , Question Author : Timmmm , Answer Author : Martin Roberts

Leave a Comment