Accelerating abelian random walks with hyperbolic dynamics

• 成果类型: Article
• 署名作者: Dubail, Bastien; Massoulie, Laurent
• 署名单位: Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Inria; Centre National de la Recherche Scientifique (CNRS); Aix-Marseille Universite
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-022-01128-x
• 发表日期: 2022
• 页码: 939-968
• 关键词: automorphisms

摘要

Given integers d >= 2, n >= 1, we consider affine random walks on torii (Z/nZ)(d) defined as Xt+1 = AX(t) + B-t mod n, where A is an element of GL(d)(Z) is a invertible matrix with integer entries and (B-t)(t >= 0) is a sequence of iid random increments on Z(d). We show that when A has no eigenvalues of modulus 1, this random walk mixes in O (log n log log n) steps as n -> infinity, and mixes actually in O (log n) steps only for almost all n. These results are similar to those of Chung et al. (Ann Probab 15(3):1148-1165, 1987) on the so-called Chung-Diaconis-Graham process, which corresponds to the case d = 1. Our proof is based on the initial arguments of Chung, Diaconis and Graham, and relies extensively on the properties of the dynamical system x bar right arrow A(inverted perpendicular) x on the continuous torus R-d /Z(d). Having no eigenvalue of modulus one makes this dynamical system a hyperbolic toral automorphism, a typical example of a chaotic system known to have a rich behaviour. As such our proof sheds new light on the speed-up gained by applying a deterministic map to a Markov chain.