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 Free Access

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?)


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.