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

Simple item page
dc.creatorAsci, Claudio
dc.date2008-05-19
dc.date.accessioned2026-07-07T09:39:42Z
dc.date.available2026-07-07T09:39:42Z
dc.descriptionThis 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 $|λ_{i}|\not=1$ for all eigenvalues $λ_{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 $λ_{i}$ that are roots of positive integer numbers, $|λ_{1}|=1$ and $|λ_{i}|>1$ for all $i\not=1$, then $O(p^{2}) $ steps are necessary and sufficient.
dc.descriptionThe published version is to appear in the Journal of Theoretical Probability
dc.identifierhttps://arxiv.org/abs/0805.2830
dc.identifierhttp://arxiv.org/abs/0805.2830
dc.identifierdoi:10.1007/s10959-008-0172-8
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/161268
dc.subjectProbability
dc.subject60B15 (Primary); 60J10 (Secondary)
dc.titleGenerating uniform random vectors in $\QTR{bf}{Z}_{p}^{k}$: the general case
dc.typetext

Files

Collections

arXiv