# Sequences similar to $\{n\alpha\}$ that are both equidistributed and truly random-like

See update at the bottom.

Here the brackets represent the fractional part, and $$\alpha \in [0, 1]$$ is a positive irrational number. It is well known that the sequences $$\{n\alpha\}$$, $$\{n^2\alpha\}$$ and more generally $$\{n^p\alpha\}$$ (with $$p$$ a strictly positive integer) are equidistributed modulo $$1$$. It is also well known that $$\{2^n\alpha\}$$ is equidistributed for almost all $$\alpha$$, indeed for all $$\alpha$$ that are normal numbers. Also these sequences are dense in $$[0,1]$$ with a uniform distribution on $$[0, 1]$$. But they are far from random: they are typically auto-correlated.

The theoretical value of the lag-$$k$$ autocorrelation $$\rho_k$$ can be computed exactly both for $$\{n\alpha\}$$ and $$\{2^n\alpha\}$$ using basic ergodic theory arguments. For the first one, see section 5.4 in one of my articles, here. There are strong long-range non-decaying autocorrelations. For the latter one, $$\rho_k=2^{-k}$$, thus autocorrelations are decaying exponentially fast. I define in the appendix what I mean by lag-$$k$$ autocorrelation.

Questions

If $$p$$ is large enough (higher than $$2$$?), do we have $$\rho_k=0$$ ($$k=1,2,\dots$$) for the sequence $$x_n=\{n^p\alpha\}$$, indexed by $$n$$? Is the sequence truly random-like? It passes a few statistical tests, but fails at the gap test (described in the appendix), unless maybe if $$p>3$$. I defined random-like in the appendix.

Even more striking, if $$p$$ is irrational (say $$p=\sqrt{7}$$) and $$\alpha=1$$, it seems that the sequence is not only equidistributed (a well known fact if I remember correctly) but also perfectly random-like and can be used for pseudo-random number generation. Not only all auto-correlations are equal to zero (it seems), but it passes the gap test and some basic independence test that I tried. See scatterplots below, where the point $$(x_n,x_{n+1})$$ represents respectively terms number $$n$$ and $$n+1$$ in the sequence.

Can this be proved or at least empirically assessed with more powerful tests or using more terms in the sequence? I only used the first $$10^4$$ terms. For large values of $$p$$, double precision is necessary, and I did not try it. Also, I only looked at independence in two dimensions. It would be great to see if it still holds in higher dimensions.

Scatterplots

The first scatterplot is for $$p=\sqrt{7},\alpha=1$$ and it suggests independence between two successive terms of the sequence. The second scatterplot is for $$p=1, \alpha=\log 2$$ and it shows total lack of independence between two successive terms of the sequence. The third scatterplot is for $$p=1.4,\alpha=\log 2$$: the red band shows an area of non-randomness; it looks much better if $$\log 2$$ is replaced by $$\sqrt{2}/2$$. Some parameters (not pictured here) create their own problems: for instance, $$p=1.5, \alpha=\sqrt{2}/2$$ results in $$x_n=0$$ for $$n=2,8,18, 32,50, 72,\dots$$

Note the X-axis represents $$x_n$$ and the Y-axis represents $$x_{n+1}$$.

Appendix

The lag-$$k$$ autocorrelation $$\rho_k$$ is defined as follows. First define $$\rho_k(n)$$ as the empirical correlation between $$(x_1,\dots,x_n)$$ and $$(x_{k+1},\dots,x_{k+n})$$. Then $$\rho_k$$ is the limit (if it exists) of $$\rho_k(n)$$ as $$n\rightarrow\infty$$.

The gap test (some people may call it run test) proceeds as follows. Let us define the binary digit $$d_n$$ as $$d_n=\lfloor 2x_n\rfloor$$. Say $$d_n=0$$ and $$d_{n+1}=1$$ for a specific $$n$$. If $$d_n$$ is followed by $$G$$ successive digits $$d_{n+1},\dots,d_{n+G}$$ all equal to $$1$$ and then $$d_{n+G+1}=0$$, we have one instance of a gap of length $$G$$. Compute the empirical distribution of these gaps. Assuming $$50\%$$ of the digits are $$0$$, the empirical gap distribution converges to a geometric distribution of parameter $$\frac{1}{2}$$ if the sequence $$x_n$$ is random-like.

A sequence is random-like if it satisfies the following property. For any finite index family $$h_1,\dots,h_k$$ and for any $$t_1,\dots,t_k\in [0,1]$$, we have

$$P(x_{n+h_1}

The probabilities are empirical probabilities, that is, based on frequency counts. For instance,

$$P(x_{n+h_1}

where $$\chi$$ is the indicator function.

Update on 11/29/2020

As @Goldstern commented, if $$p$$ is an integer, the sequence $$\{n^p\alpha\}$$ can never be perfectly random-like, though randomness might be very closely approached as $$p\rightarrow\infty$$. So a possible solution is to look at polynomials of infinite degree in $$n$$ rather than $$n^p\alpha$$, that is, Taylor series, if one wants to achieve full randomness.

I also replaced the word random by random-like since all these sequences are deterministic, creating some confusion. Initially, I wanted to use the word strongly equidistributed rather than random. I also added the definition of perfectly random-like in the appendix.

• No specific sequence is “truly random”. – Emil Jeřábek Nov 29 '20 at 9:37
• One might require that for every $k$, every nontrivial linear combination of $x_{n+1},\dots,x_{n+k}$ is equidistributed modulo 1? – YCor Nov 29 '20 at 10:13
• Are you familiar with Halton sequences, Vincent? – Gerry Myerson Nov 29 '20 at 11:33
• Remark 1: pairs $(x_n,x_{n+1})$ of successive values in the sequence $x_n=n\alpha$ (mod 1, of course) lie on a straight line, as shown in your plot. Similarly, triples $(x_n,x_{n+1},x_{n+2})$ of successive values lie on a plane if $x_n= n^2\alpha$, and a similar linear dependence exists for higher integer values of the exponent $p$ in $n^p\alpha$. – Goldstern Nov 29 '20 at 12:48
• Remark 2: If you consider the sequence $\alpha^n$ mod 1 (exponential instead of polynomial), then for almost all values $\alpha>1$ you will get a sequence $(x_n)$ such that for all $k$, the sequence $(x_{n},\ldots,x_{n+k})$ is equidistributed in $[0,1]^{k+1}$. – Goldstern Nov 29 '20 at 12:51

For any $$p>0$$ the sequence of fractional parts $$x_n=\{n^p\alpha\}$$ cannot be random-like in the sense defined in the appendix. The case of integer $$p$$ was already discussed in the comment by Goldstern. Suppose that $$k-1. Then some fixed linear combination of $$x_n,x_{n+1}\ldots,x_{n+k}$$ will approach zero as $$n \to \infty$$, so that the vectors $$(x_n,x_{n+1}\ldots,x_{n+k})$$ will asymptotically (almost) lie on a finite union of hyperplanes. For instance, if $$1 then using the Taylor expansion $$(1+u)^p=1+pu+O(u^2)$$ as $$u\to 0$$, we find that as $$n \to \infty$$, $$(n+2)^p-2(n+1)^p+n^p=n^p[(1+2/n)^p-2(1+1/n)^p+1]=n^p\cdot O(n^{-2}) \to 0 \,.$$ Thus $$x_{n+2}-2x_{n+1}+x_n \to 0$$ (If $$p=2$$ then the LHS is identically zero).

Similarly, if $$2, then use the expansion $$(1+u)^p=1+pu+{p \choose 2}u^2 + O(u^3)\; \mbox{ as } \; u\to 0 \,,$$ to infer that $$(n+3)^p-3(n+2)^p+3(n+1)^p-n^p= O(n^{p-3}) \to 0 \,.$$ (This sum is identically 0 if $$p=3$$). In general, if $$k-1, then as $$n \to \infty$$, $$\sum_{j=0}^k (-1)^j {k \choose j } (n+j)^p \to 0\,, \; \;\;\;(*)$$ so as $$n \to \infty$$, $$\sum_{j=0}^k (-1)^j {k \choose j }x_{n+j} \to 0\,.$$ The formula (*) can be deduced from the calculus of finite differences (see [1] or [2]). Alternatively, following the arguments above, use the general Binomial series $$(1+u)^p= \sum_{\ell=0}^\infty {p \choose \ell } u^\ell \mbox{ for } \; |u|<1\,,$$ (applied with $$u=j/n$$) together with the identity for integer $$0 \le \ell: $$\sum_{j=0}^k (-1)^j {k \choose j } j^\ell=0 \,$$ [1] L.M. Milne-Thomson, "The calculus of finite differences" , Macmillan (1933) Zbl 0008.01801; reprinted Dover (1981) Zbl 0477.39001 [2] Finite-difference calculus. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Finite-difference_calculus&oldid=44401

• Thank you, great answer, I will accept it in the next 48 hours. Wondering if the sequence $(\alpha^n \mod 1)$ is random-like for most $\alpha>1$. It was mentioned by Goldstern in a comment. I'd like to do some computation; if you know an efficient way to compute $\{\alpha^n\}$ for large $n$, with at least $4$ digits of accuracy e.g. if $n=10^6$ and $\alpha =2\log 2$, let me know. – Vincent Granville Nov 30 '20 at 3:32
• I am sure you know this, but let me say it anyway: For $n$ a power of 2, compute $\{\alpha^n\}$ by repeated squaring. For other $n$, use the base 2 expansion of $n$ to obtain $\{\alpha^n\}$ as product of known quantities. One difficulty is how to select a typical'' $\alpha$. Note that for Lebesgue-almost every $\alpha$ the sequence $\{2^n \alpha\}$ is equidistributed, but deciding normality for specific $\alpha$ can be hard. See, however, en.wikipedia.org/wiki/Champernowne_constant – Yuval Peres Nov 30 '20 at 18:58
• Thank you Yuval. Yes I know the trick you mentioned. I know $x_n=\{\beta\alpha^n\}$ has $x_{n+1}-\alpha x_n$ taking only finitely many values if $\beta$ is irrational and $\alpha$ is an integer, but what if $\alpha$ is irrational and $\beta=1$? Just asking because I could not observe that phenomenon with $\alpha=\log 3, \beta=1$. But I just started looking into this, so I could be wrong. – Vincent Granville Nov 30 '20 at 20:03
• Yes, for $\alpha$ irrational I don't yet know the status of $\{\alpha^n\}$. The sequence $\{\beta 2^{n^2}\}$ is random-like for almost every $\beta$, but I cannot give a specific $\beta$ which works, and this sequence is not practical computationally. – Yuval Peres Dec 2 '20 at 17:33
• The sequence $\alpha^n$ mod 1 for "typical" $\alpha$ is mentioned in the book of Knuth as a possible example of a sequence showing very strong pseudorandomness properties (but the known results are of a purely metrical nature, we do not have results for specific values of $\alpha$). See in this context H. Niederreiter and R. Tichy: Solution of a problem of Knuth on complete uniform distribution of sequences, Mathematika 32 (1985): 26 - 32, as well as this recent preprint: arxiv.org/abs/2010.10355 – Kurisuto Asutora Dec 3 '20 at 12:53

Remark 1: Pairs $$(x_n,x_{n+1})$$ of successive values in the sequence $$x_n:=n\alpha$$ (mod 1, of course) lie on a straight line, as shown in your plot. Similarly, triples $$(x_n,x_{n+1}, x_{n+2})$$ of successive values lie on a plane if $$x_n=n^2\alpha$$, and a similar linear dependence exists for higher integer values of the exponent $$p$$ in $$n^p\alpha$$. Yuval Peres points out in his answer that an approximate version of this linear dependence will even be true for non-integer values of $$p$$.

Remark 2: If you consider the sequence $$\alpha^n$$ mod 1 (exponential instead of polynomial), then for "almost all" values $$\alpha > 1$$ you will get a sequence $$(x_n)$$ such that for all $$k$$, the sequence $$(x_n,\dots, x_{n+k})$$ is is equidistributed in $$[0,1]^{k+1}$$. This will also be true if you replace $$\alpha^n$$ by $$\alpha^{b_n}$$, where $$b_n$$ is any sufficiently discrete sequence. (That is, if there is some $$\varepsilon>0$$ such that for all $$n\not=k$$ you have $$|b_n-b_k|>\varepsilon$$, or even if the number $$z_N:=\min\{ |b_n-b_k|: n\not=k \text{ and } n,k< N \}$$ does not go to $$0$$ too fast.)

Here, "almost all $$\alpha$$" means: The exceptional set of those $$\alpha>1$$ for which the statement is false has Lebesgue measure zero.

However, I don't think this is a feasible way to get "random" sequences. For starters, it can be very difficult to determine for a given $$\alpha$$ if it is in the exceptional set. As far as I know, it is even open whether the sequence $$\alpha^n$$ is equidistributed for $$\alpha:= \frac 32$$.

(Following Vincent Granville's suggestion, I combined my 2 comments into an answer.)

• thank you. Wondering if my definition of random-like sequence is equivalent to equidistribution in the unit cube $[0, 1]^k$ for all $k$. – Vincent Granville Dec 6 '20 at 0:18
• An example of $\alpha$ that fails to yield strong pseudo-randomness is $(1+\sqrt{5})/2$. Some other algebraic numbers might fail too. Almost all $\alpha$ work, but naming one explicitly may be even harder than naming one normal number explicitly, despite their abundance. – Vincent Granville Dec 6 '20 at 0:23
• @VincentGranville Indeed, see en.wikipedia.org/wiki/Pisot%E2%80%93Vijayaraghavan_number – Goldstern Dec 7 '20 at 14:29