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

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.