# zbMATH — the first resource for mathematics

Asymptotic behavior of an affine random recursion in $$\mathbf Z_p^k$$ defined by a matrix with an eigenvalue of size 1. (English) Zbl 1171.65007
Summary: We study the rate of convergence of the Markov chain $$\mathbf X_{n+1}=A\mathbf X_n+\mathbf B _n$$(mod $$p$$), where $$A$$ is an integer invertible matrix, and $$\{\mathbf B_n\}$$(mod $$p$$) is a sequence of independent and identically distributed integer vectors. If $$A$$ has an eigenvalue of size 1, then $$n=O(p^{2})$$ steps are necessary and sufficient to have $$\mathbf X_n$$ sampling from a nearly uniform distribution.

##### MSC:
 65C40 Numerical analysis or methods applied to Markov chains 60J22 Computational methods in Markov chains
##### Keywords:
convergence; Markov chain
Full Text:
##### References:
  Aldous, D.; Diaconis, P., Shuffling cards and stopping times, Amer. math. month., 93, 333-348, (1986) · Zbl 0603.60006  Asci, C., Generating uniform random vectors, J. theoret. probab., 14, 2, 333-356, (2001) · Zbl 1005.65007  Asci, C., 2009. Generating uniform random vectors in $$\mathbf{Z}_p^k$$: The general case. J. Theoret. Probab., in press (doi:10.1007/s10959-008-0172-8) · Zbl 1228.60078  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  Diaconis, P., Group representations in probability and statistics, (1988), Institute of Mathematical Statistics Hayward, California · Zbl 0695.60012  Helleloid, G., 2007. Automorphism Groups of Finite $$p$$-Groups: Structure and Applications. Ph.D. Thesis, Department of Mathematics, Stanford University  Hildebrand, M., Random processes of the form $$X_{n + 1} = a_n X_n + b_n(\operatorname{mod} p)$$, Ann. probab., 21, 2, 710-720, (1993) · Zbl 0776.60012  Hildebrand, M., 1990. Rates of Convergence of Some Random Processes on Finite Groups. Ph.D. Thesis, Department of Mathematics, Harvard University  Hildebrand, M.; McCollum, J., Generating random vectors in $$(\mathbf{Z} / p \mathbf{Z})^d$$ via an affine random process, J. theoret. probab., 21, 802-811, (2008) · Zbl 1159.65004  Knuth, D.E., The art of computer programming 2, (1981), Addison -Wesley Reading, Massachusetts · Zbl 0191.17903  Rosenthal, J.S., Convergence rates for Markov chains, SIAM rev., 37, 3, 387-405, (1995) · Zbl 0833.60069  Serre, J.P., Linear representations of finite groups, (1977), Springer-Verlag New York
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.