The uniform distribution of sequences generated by iterated polynomials
This provides a theoretical foundation for polynomial congruential generators in pseudorandom number generation, addressing a known bottleneck in ensuring uniform distribution for broader classes of polynomials.
The paper proves that sequences generated by iterating polynomials with integer coefficients converge to a uniform distribution in the s-dimensional unit cube as n increases, extending previous results limited to specific cases like s ≤ 3 and degree 2.
Assume that $m,s\in\mathbb N$, $m>1$, while $f$ is a polynomial with integer coefficients, $\text{deg}~f>1$, $f^{(i)}$ is the $i$th iteration of the polynomial $f$, $κ_n$ has a discrete uniform distribution on the set $\{0,1,\ldots,m^n - 1\}$. We are going to prove that with $n$ tending to infinity random vectors $\left(\frac{κ_n}{m^n},\frac{f(κ_n) \bmod m^n}{m^n},\ldots,\frac{f^{(s - 1)}(κ_n) \bmod m^n}{m^n}\right)$ weakly converge to a vector having a continuous uniform distribution in the $s$-dimensional unit cube. Analogous results were obtained earlier only for some classes of polynomials with $s\leqslant 3, \text{deg}~f = 2$. The mentioned vectors represent sequential pseudorandom numbers produced by a polynomial congruential generator modulo $m^n$.