Timeline for Sequences similar to $\{n\alpha\}$ that are both equidistributed and truly random-like
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 3, 2020 at 12:53 | comment | added | Kurisuto Asutora | 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 | |
| Dec 2, 2020 at 17:33 | comment | added | Yuval Peres | 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. | |
| Nov 30, 2020 at 20:03 | comment | added | Vincent Granville | 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. | |
| Nov 30, 2020 at 18:58 | comment | added | Yuval Peres | 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 | |
| Nov 30, 2020 at 15:20 | vote | accept | Vincent Granville | ||
| Nov 30, 2020 at 3:32 | comment | added | Vincent Granville | 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. | |
| Nov 30, 2020 at 1:12 | history | answered | Yuval Peres | CC BY-SA 4.0 |