Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

Author: Francis Edward Su
Journal: Trans. Amer. Math. Soc. 350 (1998), 3717-3741
MSC (1991): Primary 60J15, 60B15; Secondary 11K38, 11J70
MathSciNet review: 1467478
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 60J15, 60B15, 11K38, 11J70

Retrieve articles in all journals with MSC (1991): 60J15, 60B15, 11K38, 11J70

Additional Information

Francis Edward Su
Affiliation: Department of Mathematics, Harvey Mudd College, Claremont, California 91711

Keywords: Random walk, rate of convergence, discrepancy, Erdös-Turán inequality, continued fractions, irrational rotation, uniform distribution of sequences
Received by editor(s): October 18, 1996
Additional Notes: Supported in part by an NSF Graduate Fellowship
Article copyright: © Copyright 1998 American Mathematical Society