 |
|
|
| | | | | |
|
|
|
|
|
On the Chung-Diaconis-Graham random process
|
Martin V. Hildebrand, University at Albany, SUNY
|
Abstract
Chung, Diaconis, and Graham considered random processes of the form
Xn+1=2Xn+bn (mod p) where
X0=0, p is odd, and bn for n=0, 1, 2, ... are
i.i.d. random variables on {-1,0,1}. If
Pr(bn=-1)=Pr(bn=1)=
β and Pr(bn=0)=1-2β, they asked which value of β
makes Xn get close to uniformly distributed on the integers mod
p the slowest. In this paper, we extend the results of Chung, Diaconis,
and Graham in the case p=2t-1 to show that for
0<β≤1/2, there is no such value of β.
|
Full text: PDF
Pages: 347-356
Published on: December 15, 2006
|
Bibliography
- Chung, F. R. K.; Diaconis, Persi; Graham, R. L. Random walks arising in random number generation.
Ann. Probab. 15 (1987), no. 3, 1148--1165. MR0893921 (88d:60033)
- Diaconis, Persi. Group representations in probability and statistics.
11. Institute of Mathematical Statistics, Hayward, CA, 1988. vi+198 pp. ISBN: 0-940600-14-5 MR0964069 (90a:60001)
- Hildebrand, Martin. Random processes of the form $Xsb {n+1}=asb nXsb n+bsb npmod
Ann. Probab. 21 (1993), no. 2, 710--720. MR1217562 (94d:60012)
- Hildebrand, Martin. Random processes of the form $Xsb {n+1}=asb nXsb n+bsb npmod p$
153--174, IMA Vol. Math. Appl., 76, Springer, New York, 1996. MR1395613 (97g:60085)
|
|
|
|
|
|
|
|
| | | | |
Electronic Communications in Probability. ISSN: 1083-589X |
|
Context