5
$\begingroup$

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}$.

enter image description here

enter image description here

enter image description here

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.

$\endgroup$
8
  • 7
    $\begingroup$ No specific sequence is “truly random”. $\endgroup$ – Emil Jeřábek Nov 29 '20 at 9:37
  • 1
    $\begingroup$ One might require that for every $k$, every nontrivial linear combination of $x_{n+1},\dots,x_{n+k}$ is equidistributed modulo 1? $\endgroup$ – YCor Nov 29 '20 at 10:13
  • 1
    $\begingroup$ Are you familiar with Halton sequences, Vincent? $\endgroup$ – Gerry Myerson Nov 29 '20 at 11:33
  • 3
    $\begingroup$ 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$. $\endgroup$ – Goldstern Nov 29 '20 at 12:48
  • 4
    $\begingroup$ 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}$. $\endgroup$ – Goldstern Nov 29 '20 at 12:51
6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – Vincent Granville Nov 30 '20 at 3:32
  • $\begingroup$ 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 $\endgroup$ – Yuval Peres Nov 30 '20 at 18:58
  • $\begingroup$ 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. $\endgroup$ – Vincent Granville Nov 30 '20 at 20:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Peres Dec 2 '20 at 17:33
  • 3
    $\begingroup$ 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 $\endgroup$ – Kurisuto Asutora Dec 3 '20 at 12:53
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ thank you. Wondering if my definition of random-like sequence is equivalent to equidistribution in the unit cube $[0, 1]^k$ for all $k$. $\endgroup$ – Vincent Granville Dec 6 '20 at 0:18
  • $\begingroup$ 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. $\endgroup$ – Vincent Granville Dec 6 '20 at 0:23
  • $\begingroup$ @VincentGranville Indeed, see en.wikipedia.org/wiki/Pisot%E2%80%93Vijayaraghavan_number $\endgroup$ – Goldstern Dec 7 '20 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.