A multiplicatively symmetrized version of the Chung-Diaconis-Graham random process

Abstract: This paper considers random processes of the form

X_{n + 1} = a_{n} X_{n} + b_{n} p m o d p

where

p

is odd,

X_{0} = 0

,

(a_{0}, b_{0}), (a_{1}, b_{1}), (a_{2}, b_{2}), ...

are i.i.d., and

a_{n}

and

b_{n}

are independent with

P (a_{n} = 2) = P (a_{n} = (p + 1) / 2) = 1 / 2

and

P (b_{n} = 1) = P (b_{n} = 0) = P (b_{n} = - 1) = 1 / 3

. This can be viewed as a multiplicatively symmetrized version of a random process of Chung, Diaconis, and Graham. This paper shows that order

(l o g p)^{2}

steps suffice for

X_{n}

to be close to uniformly distributed on the integers mod

p

for all odd

p

while order

(l o g p)^{2}

steps are necessary for

X_{n}

to be close to uniformly distributed on the integers mod

p

.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: A multiplicatively symmetrized version of the Chung-Diaconis-Graham random process