×

zbMATH — the first resource for mathematics

Generating uniform random vectors in \(\mathbb Z^k_p\): the general case. (English) Zbl 1228.60078
Summary: We consider the rate of convergence of the Markov chain \({\mathbf X}_{n+1}=A{\mathbf X}_n+\mathbf B_n (\operatorname{mod} p)\), where \(A\) is an integer matrix with nonzero eigenvalues, and \(\{{\mathbf B}_n\}_n\) is a sequence of independent and identically distributed integer vectors, with support not parallel to a proper subspace of \({\mathbf Q}^k\) invariant under \(A\). If \(|\lambda_i|\neq1\) for all eigenvalues \(\lambda_i\) of \(A\), then \(n=O((\ln p)^2\)) steps are sufficient and \(n=O(\ln p)\) steps are necessary to have \({\mathbf X}_n\) sampling from a nearly uniform distribution. Conversely, if \(A\) has the eigenvalues \(\lambda_i\) that are roots of positive integer numbers, \(|\lambda_i|=1\) and \(|\lambda_i|>1\) for all \(i\neq1\), then \(O(p^2)\) steps are necessary and sufficient.

MSC:
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60F15 Strong limit theorems
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aldous, D., Diaconis, P.: Shuffling cards and stopping times. Am. Math. Mon. 93, 333–348 (1986) · Zbl 0603.60006 · doi:10.2307/2323590
[2] Asci, C.: Generating uniform random vectors. J. Theor. Probab. 14(2), 333–356 (2001) · Zbl 1005.65007 · doi:10.1023/A:1011155412481
[3] Chung, F.R.K., Diaconis, P., Graham, R.L.: Random walks arising in random number generation. Ann. Probab. 15(3), 1148–1165 (1987) · Zbl 0622.60016 · doi:10.1214/aop/1176992088
[4] Diaconis, P.: Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward (1988) · Zbl 0695.60012
[5] Helleloid, G.: Automorphism groups of finite p-groups: structure and applications. Ph.D. Thesis, Department of Mathematics, Stanford University (2007) · Zbl 1120.20025
[6] Hildebrand, M.: Random processes of the form X n+1=a n X n +b n (mod p). Ann. Probab. 21(2), 710–720 (1993) · Zbl 0776.60012 · doi:10.1214/aop/1176989264
[7] Hildebrand, M.: Rates of convergence of some random processes on finite groups. Ph.D. Thesis, Department of Mathematics, Harvard University (1990) · Zbl 0675.34037
[8] Hildebrand, M., McCollum, J.: Generating random vectors in (Z/p Z) d via an affine random process. J. Theor. Probab. (2008), doi: 10.1007/s10959-007-0135-5 · Zbl 1159.65004
[9] Knuth, D.E.: The Art of Computer Programming, vol. 2, 2nd edn. Addison-Wesley, Reading (1981) · Zbl 0477.65002
[10] Rosenthal, J.S.: Convergence rates for Markov chains. SIAM Rev. 37(3), 387–405 (1995) · Zbl 0833.60069 · doi:10.1137/1037083
[11] Serre, J.P.: Linear Representations of Finite Groups. Springer, New York (1977) · Zbl 0355.20006
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.