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

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

2008-05-19

arxiv.org/abs/0805.2830v1

Mathematics

Probability

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

Scientific paper

10.1007/s10959-008-0172-8

This paper is about the rate of convergence of the Markov chain $X_{n+1}=AX_{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}|\not=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\not=1$, then $O(p^{2}) $ steps are necessary and sufficient.

Affiliated with

Also associated with

No associations

Rating

Generating uniform random vectors in $\QTR{bf}{Z}_{p}^{k}$: the general case does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generating uniform random vectors in $\QTR{bf}{Z}_{p}^{k}$: the general case, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating uniform random vectors in $\QTR{bf}{Z}_{p}^{k}$: the general case will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-648044