On a lower bound for the Chung–Diaconis–Graham random process

Publication date: Available online 9 May 2019Source: Statistics & Probability LettersAuthor(s): Martin HildebrandAbstractConsider the random process on the integers mod p with X0=0 and Xn+1=2Xn+bn(modp) where b0,b1,b2,… are i.i.d. random variables which can have only 1, 0, and −1 as possible values. We show that unless P(bn=0)=1∕2 or P(bn=1)=P(bn=−1)=1∕2, then for some C>1 depending on the probability distribution for bn, at least Clog2p steps are needed to make Xn close to uniformly distributed.

Source: Statistics and Probability Letters - May 13, 2019 Category: Statistics Source Type: research