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

DOI10.1007/S10959-007-0135-5zbMATH Open1159.65004arXivmath/0701570OpenAlexW2112525161MaRDI QIDQ960177FDOQ960177

Authors: Joseph McCollum, Martin V. Hildebrand 

Publication date: 16 December 2008

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random walks arising in random number generation
• The Asymptotic Behavior of the Solutions of a Class of Differential-Difference Equations
• Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
• Generating uniform random vectors
• Title not available (Why is that?)

Cited In (13)

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