Document Type



Mathematics (HMC)

Publication Date



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.


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.