# 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
Full Text:
##### References:
  Aldous, D., Diaconis, P.: Shuffling cards and stopping times. Am. Math. Mon. 93, 333–348 (1986) · Zbl 0603.60006 · doi:10.2307/2323590  Asci, C.: Generating uniform random vectors. J. Theor. Probab. 14(2), 333–356 (2001) · Zbl 1005.65007 · doi:10.1023/A:1011155412481  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  Diaconis, P.: Group Representations in Probability and Statistics. Institute of Mathematical Statistics, Hayward (1988) · Zbl 0695.60012  Helleloid, G.: Automorphism groups of finite p-groups: structure and applications. Ph.D. Thesis, Department of Mathematics, Stanford University (2007) · Zbl 1120.20025  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  Hildebrand, M.: Rates of convergence of some random processes on finite groups. Ph.D. Thesis, Department of Mathematics, Harvard University (1990) · Zbl 0675.34037  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  Knuth, D.E.: The Art of Computer Programming, vol. 2, 2nd edn. Addison-Wesley, Reading (1981) · Zbl 0477.65002  Rosenthal, J.S.: Convergence rates for Markov chains. SIAM Rev. 37(3), 387–405 (1995) · Zbl 0833.60069 · doi:10.1137/1037083  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.