Accelerating Abelian Random Walks with Hyperbolic Dynamics

Abstract

Given integers $d\ge 2,n\ge 1$, we consider affine random walks on torii $(\mathbb{Z}/n\mathbb{Z}{)}^d$ defined as $X_{t+1}=A{X}_t+B_t\mathrm{mod}n$, where $A\in {\mathrm{GL}}_d(\mathbb{Z})$ is an invertible matrix with integer entries and $(B_t{)}_{t\ge 0}$ is a sequence of iid random increments on ${\mathbb{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\to \infty$, and mixes actually in $O(\log n)$ steps only for almost all $n$. These results generalize those 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\mapsto A^{\top }x$ on the continuous torus ${\mathbb{R}}^d/{\mathbb{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.

28 pages. Fixed a proof in the first version. Accepted for publication in PTRF