Generating uniform random vectors (Q5939305): Difference between revisions

The author investigates the properties of the Markov chain \(X_{n+1} = AX_n+b_n \mod p\), where \(b_i\) are identically distributed independent random integer vectors of dimension \(m\), \(A\) is an \(m\)-dimensional integer matrix and \(p\) a prime number. The paper deals mainly with the case when \(A\) is regular. The main result says that if no eigenvalues of \(A\) are equal to \(\pm 1\) then \(O(\log(p))\) steps are necessary and \(O(\log(p)^2)\) steps are sufficient for \(X_n\) to be nearly uniformly distributed. If some eigenvalues have value \(1\) or \(-1,\) then both limits are \(O(p^2)\). The paper contains many technical results. No examples and directly applicable numerical results and/or algorithms are presented.