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

Question

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}<t_1, \dots, x_{n+h_k}<t_k) =\prod_{j=1}^k P(x_{n+h_j}<t_j)=\prod_{j=1}^k t_j.$$

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

$$P(x_{n+h_1}<t_1, x_{n+h_2}<t_2)=\lim_{m\rightarrow\infty} \Big(\frac{1}{m}\sum_{j=1}^m \chi(x_{j+h_1}<t_1, x_{j+h_2}<t_2)\Big)$$

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.

Answer 1

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<p \le k$. 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<p<2$ 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<p<3$, 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<p \le k$, 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<k$: $$\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

Answer 2

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