Convergence of random walks on the circle generated by an irrational rotation

Abstract:

Fix $\alpha \in [0,1)$. Consider the random walk on the circle $S^1$ which proceeds by repeatedly rotating points forward or backward, with probability $\frac 12$, by an angle $2\pi \alpha$. This paper analyzes the rate of convergence of this walk to the uniform distribution under “discrepancy” distance. The rate depends on the continued fraction properties of the number $\xi =2\alpha$. We obtain bounds for rates when $\xi$ is any irrational, and a sharp rate when $\xi$ is a quadratic irrational. In that case the discrepancy falls as $k^{-\frac 12}$ (up to constant factors), where $k$ is the number of steps in the walk. This is the first example of a sharp rate for a discrete walk on a continuous state space. It is obtained by establishing an interesting recurrence relation for the distribution of multiples of $\xi$ which allows for tighter bounds on terms which appear in the Erdős-Turán inequality.