Generating random vectors in ( Z/ p Z)^d via an affine random process

DOI10.1007/S10959-007-0135-5MaRDI QIDQ960177zbMATHOpenAlexFDO

Authors Joseph McCollum, Martin V. Hildebrand

Publication date 16 December 2008

Published in Journal of Theoretical Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0701570

zbMATH Keywords

Fourier transformrandom processesrandom vector generationupper bound lemma

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) General theory of stochastic processes (60G07)

Abstract: This paper considers some random processes of the form X_{n+1}=TX_n+B_n (mod p) where B_n and X_n are random variables over (Z/pZ)^d and T is a fixed d x d integer matrix which is invertible over the complex numbers. For a particular distribution for B_n, this paper improves results of Asci to show that if T has no complex eigenvalues of length 1, then for integers p relatively prime to det(T), order (log p)^2 steps suffice to make X_n close to uniformly distributed where X_0 is the zero vector. This paper also shows that if T has a complex eigenvalue which is a root of unity, then order p^b steps are needed for X_n to get close to uniform where b is a value which may depend on T and X_0 is the zero vector.

Recommendations

• Generating uniform random vectors in \(\mathbb Z^k_p\): the general case
• Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
• Generating uniform random vectors
• scientific article; zbMATH DE number 850233
• A lower bound for the Chung-Diaconis-Graham random process

Cites work

• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 607286 (Why is no real title available?)
• scientific article; zbMATH DE number 850233 (Why is no real title available?)
• Generating uniform random vectors
• Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
• Random walks arising in random number generation
• The Asymptotic Behavior of the Solutions of a Class of Differential-Difference Equations

Cited in

(13)

• Generating uniform random vectors
• A multiplicatively symmetrized version of the Chung-Diaconis-Graham random process
• Random motion on finite rings. I: commutative rings
• Asymptotic behavior of an affine random recursion in \(\mathbf Z_p^k\) defined by a matrix with an eigenvalue of size 1
• On a lower bound for the Chung-Diaconis-Graham random process
• Generating uniform random vectors in \(\mathbb Z^k_p\): the general case
• Random walks on rings and modules
• Some things we've learned (about Markov chain Monte Carlo)
• Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
• A random process for the construction of multiaffine fields
• Accelerating abelian random walks with hyperbolic dynamics
• Convergence of transition matrices of some Markov chains on finite abelian group to the uniform matrix
• A lower bound for the Chung-Diaconis-Graham random process

This page was built for publication: Generating random vectors in \((\mathbb Z/ p \mathbb Z)^d\) via an affine random process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q960177)