×

zbMATH — the first resource for mathematics

Generating random vectors in \((\mathbb Z/ p \mathbb Z)^d\) via an affine random process. (English) Zbl 1159.65004
The work improves some results of C. Asci [J. Theor. Probab. 14, No. 2, 333–356 (2001; Zbl 1005.65007)], and continues with previous works of the first author; for example, see M. Hildebrand [Ann. Probab. 21, No. 2, 710–720 (1993; Zbl 0776.60012)]. The authors consider the random processes \(\mathbf X_{n+1}=T\mathbf X_n+\mathbf B_n\pmod p\) where \(\mathbf B_n\) and \(\mathbf X_n\) are random variables over \((\mathbb Z/p\mathbb Z)^d\) and \(T\) is a fixed \(d\times d\) integer matrix which is invertible over \(\mathbb C\). If \(T\) has no eigenvalues of modulus \(1\) over \(\mathbb C\), sufficient conditions are given to make \(\mathbf X_n\) close to uniformly distributed. In case \(T\) has a complex eigenvalue which is a root of unity, necessary conditions are given.

MSC:
65C10 Random number generation in numerical analysis
60G07 General theory of stochastic processes
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Asci, C.: Generating uniform random vectors. J. Theor. Probab. 14, 333–356 (2001) · Zbl 1005.65007 · doi:10.1023/A:1011155412481
[2] Chung, F., Diaconis, P., Graham, R.: A random walk problem arising in random number generation. Ann. Probab. 15, 1148–1165 (1987) · Zbl 0622.60016 · doi:10.1214/aop/1176992088
[3] Diaconis, P.: Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward (1988) · Zbl 0695.60012
[4] Greenhalgh, A.: Random walks on groups with subgroup invariance properties. Ph.D. thesis, Stanford University, Department of Mathematics (1989)
[5] Hildebrand, M.: Rates of convergence of some random processes on finite groups. Ph.D. thesis, Harvard University, Department of Mathematics (1990) · Zbl 0675.34037
[6] Hildebrand, M.: Random processes of the form X n+1=a n X n +b n (mod p). Ann. Probab. 21, 710–720 (1993) · Zbl 0776.60012 · doi:10.1214/aop/1176989264
[7] Hildebrand, M.: Random processes of the form X n+1=a n X n +b n (mod p) where b n takes on a single value. In: Aldous, Pemantle (eds.) Random Discrete Structures, pp. 153–174. Springer, New York (1996) · Zbl 0840.60058
[8] Knuth, D.: The Art of Computer Programming, vol. II, 2nd edn. Addison-Wesley, Menlo Park (1981) · Zbl 0477.65002
[9] Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications, revised edn. Cambridge University Press, Cambridge (1994) · Zbl 0820.11072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.