## On the Chung-Diaconis-Graham random process.(English)Zbl 1132.60006

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.

### MSC:

 60B15 Probability measures on groups or semigroups, Fourier transforms, factorization 60J10 Markov chains (discrete-time Markov processes on discrete state spaces)

### Keywords:

random processes; discrete Fourier analysis
Full Text: