Generating uniform random vectors in $\QTR{bf}{Z}_{p}^{k}$: the general case

Abstract

This paper is about the rate of convergence of the Markov chain $X_{n+1}=A{X}_n+B_n$ (mod $p$), where $A$ is an integer matrix with nonzero eigenvalues and ${B_n}_n$ is a sequence of independent and identically distributed integer vectors, with support not parallel to a proper subspace of $Q^k$ invariant under $A$. If $|{\lambda }_i|\ne 1$ for all eigenvalues ${\lambda }_i$ of $A$, then $n=O((\ln p{)}^2)$ steps are sufficient and $n=O(\ln p)$ steps are necessary to have $X_n$ sampling from a nearly uniform distribution. Conversely, if $A$ has the eigenvalues ${\lambda }_i$ that are roots of positive integer numbers, $|{\lambda }_1|=1$ and $|{\lambda }_i|>1$ for all $i\ne 1$, then $O(p^2)$ steps are necessary and sufficient.

The published version is to appear in the Journal of Theoretical Probability

References in corpus (1)

• Automorphism Groups of Finite p-Groups: Structure and Applications