Mixing time of the Chung–Diaconis–Graham random process

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 in Ann Probab 15(3):1148–1165, 1987), and at least $$1.004 \log _2 q$$ (Hildebrand in Proc Am Math Soc 137(4):1479–1487, 2009). 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$$ .