Mixing time of the Chung--Diaconis--Graham random process

Abstract

Define $(X_n)$ on $\mathbf{Z}/q\mathbf{Z}$ by $X_{n+1}=2X_n+b_n$, where the steps $b_n$ are chosen independently at random from $-1,0,+1$. The mixing time of this random walk is known to be at most $1.02{\log }_{2}q$ for almost all odd $q$ (Chung--Diaconis--Graham, 1987), and at least $1.004{\log }_{2}q$ (Hildebrand, 2008). We identify a constant $c=1.01136\dots$ such that the mixing time is $(c+o(1)){\log }_{2}q$ for almost all odd $q$. In general, the mixing time of the Markov chain $X_{n+1}=a{X}_n+b_n$ modulo $q$, where $a$ is a fixed positive integer and the steps $b_n$ are i.i.d. with some given distribution in $\mathbf{Z}$, is related to the entropy of a corresponding self-similar Cantor-like measure (such as a Bernoulli convolution). We estimate the mixing time up to a $1+o(1)$ factor whenever the entropy exceeds $(\log a)/2$.

26 pages, version accepted for publication in Probab. Theory Related Fields; minor corrections based on referee's report; results and proofs are not changed

Cited by in corpus (4)

• Markov chains on finite fields with deterministic jumps
• Universality for low degree factors of random polynomials over finite fields
• The square and add Markov chain
• Cutoff for random walk on random graphs with a community structure