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

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$.