Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A lower bound for the Chung-Diaconis-Graham random process


Author: Martin Hildebrand
Journal: Proc. Amer. Math. Soc. 137 (2009), 1479-1487
MSC (2000): Primary 60C05; Secondary 60B15
DOI: https://doi.org/10.1090/S0002-9939-08-09687-1
Published electronically: November 3, 2008
MathSciNet review: 2465674
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Chung, Diaconis, and Graham considered random processes of the form $ X_{n+1}=a_nX_n+b_n\pmod p$ where $ p$ is odd, $ X_0=0$, $ a_n=2$ always, and $ b_n$ are i.i.d. for $ n=0,1,2,\dots$. In this paper, we show that if $ P(b_n=-1)=P(b_n=0)=P(b_n=1)=1/3$, then there exists a constant $ c>1$ such that $ c\log_2p$ steps are not enough to make $ X_n$ get close to being uniformly distributed on the integers mod $ p$.


References [Enhancements On Off] (What's this?)

  • 1. Asci, C. ``Generating uniform random vectors''. J. Theoret. Probab. 14 (2001), 333-356. MR 1838732 (2002c:60115)
  • 2. Chung, F., Diaconis, P., and Graham, R. ``Random walks arising in random number generation''. Ann. Probab. 15 (1987), 1148-1165. MR 893921 (88d:60033)
  • 3. Durrett, R. Probability: Theory and Examples, third edition. Wadsworth & Brooks/Cole, Pacific Grove, CA, 2005. MR 1068527 (91m:60002)
  • 4. Hildebrand, M. ``Random processes of the form $ X_{n+1}=a_nX_n+b_n\pmod p$''. Ann. Probab. 21 (1993), 710-720. MR 1217562 (94d:60012)
  • 5. Hildebrand, M. ``Random processes of the form $ X_{n+1}= a_nX_n+b_n\pmod p$ where $ b_n$ takes on a single value''. pp. 153-174, Random Discrete Structures, ed. Aldous and Pemantle. Springer-Verlag, New York, 1996. MR 1395613 (97g:60085)
  • 6. Hildebrand, M. ``On the Chung-Diaconis-Graham random process''. Electron. Commun. Probab. 11 (2006), 347-356. MR 2274529 (2008g:60017)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 60C05, 60B15

Retrieve articles in all journals with MSC (2000): 60C05, 60B15


Additional Information

Martin Hildebrand
Affiliation: Department of Mathematics and Statistics, University at Albany, State University of New York, Albany, New York 12222

DOI: https://doi.org/10.1090/S0002-9939-08-09687-1
Received by editor(s): June 2, 2008
Published electronically: November 3, 2008
Communicated by: Richard C. Bradley
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society