Random Processes of the Form $X_{n+1} = a_nX_n + b_n (\mod p)$
Hildebrand, Martin
Ann. Probab., Tome 21 (1993) no. 4, p. 710-720 / Harvested from Project Euclid
This paper considers random processes of the form $X_{n + 1} = a_nX_n + b_n (\operatorname{mod} p)$, where $X_0 = 0$ and the sequences $a_n$ and $b_n$ are independent with $a_n$ identically distributed for $n = 0, 1, 2, \ldots$ and $b_n$ identically distributed for $n = 0, 1, 2, \ldots$. Chung, Diaconis and Graham studied such processes where $a_n = 2$ always; this paper considers more general distributions for $a_n$ and $b_n$. The question is how long does it take these processes to get close to the uniform distribution? If $a_n$ is a distribution on $\mathbf{Z}^+$ which does not vary with $p$ and $b_n$ is a distribution on $\mathbf{Z}$ which also does not vary with $p$, an upper bound on this time is $O((\log p)^2)$ with appropriate restrictions on $p$ unless $a_n = 1$ always, $b_n = 0$ always or $a_n$ and $b_n$ can each take on only one value. This paper uses a recursive relation involving the discrete Fourier transform to find the bound. Under more restrictive conditions for $a_n$ and $b_n$, this paper finds that a generalization of the technique of Chung, Diaconis and Graham shows that $O(\log p \log \log p)$ steps suffice.
Publié le : 1993-04-14
Classification:  Random processes,  Fourier transform,  convergence,  uniform distribution,  upper bound lemma,  recursion,  60B15,  60J15
@article{1176989264,
     author = {Hildebrand, Martin},
     title = {Random Processes of the Form $X\_{n+1} = a\_nX\_n + b\_n (\mod p)$},
     journal = {Ann. Probab.},
     volume = {21},
     number = {4},
     year = {1993},
     pages = { 710-720},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176989264}
}
Hildebrand, Martin. Random Processes of the Form $X_{n+1} = a_nX_n + b_n (\mod p)$. Ann. Probab., Tome 21 (1993) no. 4, pp.  710-720. http://gdmltest.u-ga.fr/item/1176989264/