On the Chung-Diaconis-Graham random process (Q2461005)

Let \(Pr(b_n=1)=a\), \(Pr(b_n=0)=b\) and \(Pr(b_n=-1)=c\), \(a+b+c=1\), \(a,b\) and \(c\) are less than 1. Suppose \(b_0,b_1,b_2,\ldots \) are i.i.d. and \(X_0=0\), \(X_{n+1}=2X_n+b_n\) (mod \(p\)) and \(p\) is odd. Let \(P_n(s)=Pr(X_n=s)\). The paper proves: 1. Suppose either \(b=0\) and \(a=c=1/2\) or \(b=1/2\). If \(n>c_1\log _2p\) where \(c_1>1\) is constant, then \(\| P_n-U\| \to 0\) as \(p\to \infty \) where \(p\) is an odd integer. 2. Suppose \(a,b\) and \(c\) do not satisfy the previous conditions. Then there exists a value \(c_2\) (depending on \(a,b\) and \(c\)) such that if \(n<c_2(\log p)\log (\log p)\) and \(p=2^t-1\), then \(\| P_n-U\| \to 1\) as \(t\to \infty \). Here \(\| P-U\| \) is the variation distance, \(U\) the uniform distribution.