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

DOI10.1090/S0002-9939-08-09687-1MaRDI QIDQ3623363zbMATH OpenFDO

Authors Martin V. Hildebrand

Publication date 17 April 2009

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.3094

Mathematics Subject Classification ID

Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Combinatorial probability (60C05)

Abstract: Chung, Diaconis, and Graham considered random processes of the form X_{n+1}=a_n X_n+b_n (mod p) where p is odd, X_0=0, a_n=2 always, and b_n are i.i.d. for n=0,1,2,... . 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_2 p steps are not enough to make X_n get close to uniformly distributed on the integers mod p.

Recommendations

• On a lower bound for the Chung-Diaconis-Graham random process
• On the Chung-Diaconis-Graham random process
• A multiplicatively symmetrized version of the Chung-Diaconis-Graham random process
• Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
• Generating random vectors in ( Z/ p Z)^d via an affine random process

Cites work

• Generating uniform random vectors
• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 850233 (Why is no real title available?)
• On the Chung-Diaconis-Graham random process
• Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
• Random walks arising in random number generation

Cited in

(16)

• Random walks on rings and modules
• Correction to: ``Speeding up Markov chains with deterministic jumps
• Mixing time of fractional random walk on finite fields
• Accelerating abelian random walks with hyperbolic dynamics
• Markov chains on finite fields with deterministic jumps
• A multiplicatively symmetrized version of the Chung-Diaconis-Graham random process
• Speeding up Markov chains with deterministic jumps
• On a lower bound for the Chung-Diaconis-Graham random process
• On the Chung-Diaconis-Graham random process
• Mixing time of the Chung-Diaconis-Graham random process
• Convergence of transition matrices of some Markov chains on finite abelian group to the uniform matrix
• Some things we've learned (about Markov chain Monte Carlo)
• The Generic Chaining
• On the multiplicative Chung-Diaconis-Graham process
• Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
• Generating random vectors in ( Z/ p Z)^d via an affine random process

This page was built for publication: A lower bound for the Chung-Diaconis-Graham random process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3623363)