## Abstract

Define (X_{n}) on Z/ qZ by X_{n}_{+}_{1}= 2 X_{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 ⋯ 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}= aX_{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 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.

Original language | English |
---|---|

Pages (from-to) | 317-344 |

Number of pages | 28 |

Journal | Probability Theory and Related Fields |

Volume | 179 |

Issue number | 1-2 |

Early online date | 10 Oct 2020 |

DOIs | |

Publication status | Published - Feb 2021 |

Externally published | Yes |

### Bibliographical note

Funding Information:Sean Eberhard and Péter P. Varjú have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 803711). PV was supported by the Royal Society.

Publisher Copyright:

© 2020, Springer-Verlag GmbH Germany, part of Springer Nature.

## ASJC Scopus subject areas

- Analysis
- Statistics and Probability
- Statistics, Probability and Uncertainty