×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aldous, D.; Diaconis, P., Shuffling cards and stopping times, Amer. math. month., 93, 333-348, (1986) · Zbl 0603.60006
[2] Asci, C., Generating uniform random vectors, J. theoret. probab., 14, 2, 333-356, (2001) · Zbl 1005.65007
[3] 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
[4] 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
[5] Diaconis, P., Group representations in probability and statistics, (1988), Institute of Mathematical Statistics Hayward, California · Zbl 0695.60012
[6] Helleloid, G., 2007. Automorphism Groups of Finite \(p\)-Groups: Structure and Applications. Ph.D. Thesis, Department of Mathematics, Stanford University
[7] 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
[8] Hildebrand, M., 1990. Rates of Convergence of Some Random Processes on Finite Groups. Ph.D. Thesis, Department of Mathematics, Harvard University
[9] 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
[10] Knuth, D.E., The art of computer programming 2, (1981), Addison -Wesley Reading, Massachusetts · Zbl 0191.17903
[11] Rosenthal, J.S., Convergence rates for Markov chains, SIAM rev., 37, 3, 387-405, (1995) · Zbl 0833.60069
[12] 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.