Generating uniform random vectors (Q5939305)
From MaRDI portal
scientific article; zbMATH DE number 1625589
Language | Label | Description | Also known as |
---|---|---|---|
English | Generating uniform random vectors |
scientific article; zbMATH DE number 1625589 |
Statements
Generating uniform random vectors (English)
0 references
4 February 2003
0 references
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.
0 references
Markov chains
0 references
random vector generation
0 references
linear congruent generators
0 references