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

Asci, Claudio

Stat. Probab. Lett. 79, No. 11, 1421-1428 (2009).

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

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