The lattice structure of pseudo-random vectors generated by matrix generators (Q1111312): Difference between revisions

For use of Monte Carlo methods in solving problems with many independent random variables often pseudo-random number generators are applied which supply successively numbers with sufficient independency, when taken as n-tuples. A mean to assess the sufficiency is to consider for \(n=1,2,..\). these n-tuples as points \((x_ 1,...,x_ n)\) of \({\mathbb{R}}_ n\) restricted to the volume of distribution, or, in case of linear congruential generators with factor p (some large prime), more preferably as points of \({\mathbb{Z}}_ p^{\times n}\), the n-dimensional space over the finite Galois field GF(p) of order p \(\{\) that means \(x_ k\in \{0,1,...,p-1\}).\) This article advocates the earlier proposed generator \(x^{(i+1)}=Ax^{(i)}\), wherein the \(x^{(i)}\) are (equivalent to) r- tuples and A an \(r\times r\) matrix from GF(p), the latter of the highest possible order \(p^ r-1\), and examines the accordingly generalized distribution of the n-tuples of \(x^{(i)}\) which turns out as it should be as a lattice in \({\mathbb{Z}}_ p^{\times r\cdot n}\). The estimators suggested are the so-called Beyer quotients \(q_ k\) defined as the maximal dilatation of a fundamental k-corner with k-shortest edges of the lattice embedded in \({\mathbb{R}}_ k\). Examples of numerical results point to the need for further investigations. Note: The order of computational expense for m random numbers - except in case of very sparse A - proportional to \(m^ 2\) compared to m when using ordinary linear generators.