1
$\begingroup$

I am investing the randomness properties of the sequence $y_n=\bmod(x_n,c)$ with $c=2$ and

$$x_{n+1} = x_n +\sum_{k=1}^r a_k\bmod(x_n,p_k)+\sum_{k=1}^r b_k\bmod(n+1,p_k).$$

The initial value is $x_1$, and $p_1,p_2$ and so on are the prime numbers, with $p_1=2$. Also, $a_k,b_k\in \{-1, 0, 1\}$. I've spent a bit of time on the case $r=8, x_1=3$, with the following coefficients:

\begin{array}{|c|cccccccc|} \hline k & 1& 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline p_k & 2& 3 & 5 & 7 & 11 & 13 & 17 & 19\\ a_k& -1 & 1 & 1 & 1 & -1 & -1 & 0 & 1\\ b_k& -1 & -1 & -1 & -1& 1& 1 & 0 & -1\\ \hline \end{array}

Very little memory is needed to generate the $x_n$'s. So far I run only a few tests to check randomness (mostly the runs test). It seems to do fine and period-free up until some very large $n$. Then, all of a sudden the difference $x_{n+1}-x_n$ becomes permanently constant. In my example, I don't know when that happens, it must be for $n>10^8$ and maybe much larger. But with smaller values of $r$ (say $r=3$) this becomes apparent quite early.

My question

Is the behavior described above always the case regardless of the coefficients, $x_1$ and $r$? In other words, is it impossible to build a non-periodic generator with my method, even though the very short period may kick in after a very large number of iterations (just like the binary digits of a rational number may not start showing a period until after a lot of digits)? And of course, I'd like to know when exactly (or get some bounds) on the value of $n$ when the period starts, especially in the example discussed above.

$\endgroup$
3
  • 2
    $\begingroup$ I've checked your $r=8$ case and found a period of at most $19\#$. The $r=3$ case with $p=\{2, 3, 5\}$ also shows a period of $30=5\#$. It's possible that your PRNG with output $x_{n+1}-x_n$ will eventually enter a period of $\prod p_k$ regardless of the coefficients. $\endgroup$ Nov 17, 2021 at 2:08
  • $\begingroup$ You are right, the period seems to be $2\times 3 \times 5 \times 7 \times 11 \times 13 \times 19$. But if you remove $19$ and use $17$ with $a_7=1,b_7=-1$, the period is only $2$, but it starts after more than $7\times 10^6$ iterations. If you keep $19$ unchanged with same coefficients, do not use $17$, and add $23$ with $a_9=-1, b_9=1$, I have no idea what the period is, how big or small it is or even if there is one. But if there is one, it must starts after $10^9$ iterations. $\endgroup$ Nov 17, 2021 at 5:17
  • 1
    $\begingroup$ For the case with additional $\{p_9=23, a_9=-1, b_9=1\}$, the period is $643032390=2\times3\times5\times7^3\times11\times13\times19\times23$. The scaling factor of $49$ comes from nowhere. $\endgroup$ Nov 17, 2021 at 7:31

1 Answer 1

0
$\begingroup$

This is a partial solution too long for a comment, but too incomplete to be an answer.

Considering the second summation over a period of $P=\prod p_k$: $$ \begin{align*} \sum_{i=1}^P\sum_{k=1}^r b_k\operatorname{mod}(n+i, p_k)&=\sum_{k=1}^r\left(b_k\sum_{i=1}^P\operatorname{mod}(n+i, p_k)\right)\\ &=\sum_{k=1}^r\left(b_k\cdot\frac{P}{p_k}\cdot\frac{p_k(p_k-1)}2\right)\\ &=\sum_{k=1}^r\frac{b_kP(p_k-1)}2 \end{align*} $$ which is a constant derivable from the coefficients.

Considering again the whole iteration formula over a period of $P$, $$ \begin{align*} x_{n+P}&=x_n+\sum_{i=1}^P\sum_{k=1}^r a_k\operatorname{mod}(x_{n+i-1}, p_k)+\sum_{i=1}^P\sum_{k=1}^r b_k\operatorname{mod}(n+i, p_k)\\ &=x_n+\sum_{i=1}^P\sum_{k=1}^r a_k\operatorname{mod}(x_{n+i-1}, p_k)+\text{some constant} \end{align*} $$ then what's left is to prove that whether the first summation turns out to be constant.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .