Mixing time of the Chung-Diaconis-Graham random process

• 成果类型: Article
• 署名作者: Eberhard, Sean; Varju, Peter P.
• 署名单位: University of Cambridge
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-020-01009-1
• 发表日期: 2021
• 页码: 317-344
• 关键词: random-walks

摘要

Define (X-n) on Z/qZ by Xn+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 ... 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.