Mixing time of the Chung-Diaconis-Graham random process (Q2660392): Difference between revisions

The paper considers mixing time of the Markov chain \({X_{n + 1}} = a{X_n} + {b_n}\) (modulo \(q\)), \({X_0} = 0\) where \(a > 1\) is a positive integer and \({b_1},{b_2},\ldots\) are i.i.d. random variables distributed according to a finitely supported measure \(\mu \) on \(\mathbb Z\), not supported on a coset of a proper subgroup. The main theorem establishes a relation between the mixing time of \({X_n}\) and the entropy of a corresponding self-similar Cantor-like measure. It permits the authors to estimate the mixing time up to a \(1 + o(1)\) factor whenever the entropy exceeds \({2^{ - 1}}\log a\). In the case of \(a = 2\) and \({b_n} \in \{ - 1,0,1\} \), they identify a constant \(c = 1.01136\ldots\) such that the mixing time is \((c + o(1)){\log _2}q\) for almost all odd \(q\).