Convergence of Random Walks on the Circle Generated by an Irrational Rotation

Authors

Francis E. Su, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1998

Abstract

Fix . Consider the random walk on the circle which proceeds by repeatedly rotating points forward or backward, with probability , by an angle . 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 . We obtain bounds for rates when is any irrational, and a sharp rate when is a quadratic irrational. In that case the discrepancy falls as (up to constant factors), where 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 which allows for tighter bounds on terms which appear in the Erdös-Turán inequality.

Comments

Archived with permission from the American Mathematical Society.

Rights Information

© 1998 American Mathematical Society.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1090/S0002-9947-98-02152-7

Recommended Citation

Francis Edward Su. “Convergence of random walks on the circle generated by an irrational rotation”. Trans. Amer. Math. Soc., 350(9) (1998):3717–3741. © 1998 by the American Mathematical Society.