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

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

2008-01-20

arxiv.org/abs/0801.3094v2

Mathematics

Probability

10 pages; this version makes a small change on p. 6

Scientific paper

Chung, Diaconis, and Graham considered random processes of the form X_{n+1}=a_n X_n+b_n (mod p) where p is odd, X_0=0, a_n=2 always, and b_n are i.i.d. for n=0,1,2,... . 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_2 p steps are not enough to make X_n get close to uniformly distributed on the integers mod p.

Affiliated with

Also associated with

No associations

Rating

A lower bound for the Chung-Diaconis-Graham random process does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A lower bound for the Chung-Diaconis-Graham random process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A lower bound for the Chung-Diaconis-Graham random process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-384683