Random Walks Arising in Random Number Generation
Chung, F. R. K. ; Diaconis, Persi ; Graham, R. L.
Ann. Probab., Tome 15 (1987) no. 4, p. 1148-1165 / Harvested from Project Euclid
Random number generators often work by recursively computing $X_{n+1} \equiv aX_n + b (\mod p)$. Various schemes exist for combining these random number generators. In one scheme, $a$ and $b$ are themselves chosen each time from another generator. Assuming that this second source is truly random, we investigate how long it takes for $X_n$ to become random. For example, if $a = 1$ and $b = 0, 1$, or $-1$ each with probability $\frac{1}{3}$, then $cp^2$ steps are required to achieve randomness. On the other hand, if $a = 2$ and $b = 0, 1$, or $-1$, each with probability $\frac{1}{3}$, then $c \log p \log\log p$ steps always suffice to guarantee randomness, and for infinitely many $p$, are necessary as well, although, in fact, for almost all odd $p, 1.02 \log_2 p$ steps are enough.
Publié le : 1987-07-14
Classification:  Random walk,  Fourier analysis,  discrete Fourier analysis,  random number generation,  60B15,  60J15
@article{1176992088,
     author = {Chung, F. R. K. and Diaconis, Persi and Graham, R. L.},
     title = {Random Walks Arising in Random Number Generation},
     journal = {Ann. Probab.},
     volume = {15},
     number = {4},
     year = {1987},
     pages = { 1148-1165},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176992088}
}
Chung, F. R. K.; Diaconis, Persi; Graham, R. L. Random Walks Arising in Random Number Generation. Ann. Probab., Tome 15 (1987) no. 4, pp.  1148-1165. http://gdmltest.u-ga.fr/item/1176992088/