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

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?)

  • 1. D. Asimov, The grand tour, SIAM Jour. Sci. Statist. Comp. 6(1983), 128-143. MR 86h:62087
  • 2. P. Diaconis, Group Representations in Probability and Statistics, Institute of Mathematical Statistics Lecture Notes, Vol. 11, Hayward, CA, 1988. MR 90a:60001
  • 3. P. Diaconis and L. Saloff-Coste, Comparison Techniques for Random Walks on Finite Groups, Ann. Probab. 21(1993), 2131-2156. MR 95a:60009
  • 4. P. Erd\H{o}s and P. Turán, On a problem in the theory of uniform distribution I, Indag. Math. 10(1948), 370-378. MR 10:372c
  • 5. B.M. Kloss, Limiting distributions on bicompact topological groups, Th. Probab. Appl. 4(1959), 237-270.
  • 6. A.Ya. Khinchin, Continued Fractions, Univ. of Chicago Press, 1964. MR 28:5037
  • 7. L. Kuipers and H. Neiderreiter, Uniform Distribution of Sequences, Wiley, New York, 1974. MR 54:7415
  • 8. S. Lang, Introduction to Diophantine Approximations, Springer-Verlag, 1995. MR 96h:11067
  • 9. W.J. LeVeque, An inequality connected with Weyl's criterion for uniform distribution, Proc. Symp. Pure Math. 8(1965), 22-30. MR 31:3401
  • 10. A. Lubotsky, R. Phillips, and P. Sarnak, Hecke Operators and Distributing Points on the Sphere, I, Comm. Pure. Appl. Math. 39(1986), S149-S186. MR 88m:11025a
  • 11. J. Marsden, Elementary Classical Analysis, W.H. Freeman and Co., 1974. MR 50:10161
  • 12. Mathematica, version 2. Wolfram Research, Inc., 1991.
  • 13. P. Matthews, Covering problems for random walks on spheres and finite groups, Ph.D. Thesis, Dept. of Statistics, Stanford Univ., 1985.
  • 14. H. Niederreiter and W. Philipp, Berry-Esseen bounds and a theorem of Erd\H{o}s and Turán on uniform distribution mod 1, Duke Math. J. 40(1973), 633-649. MR 49:2642
  • 15. U. Porod, The cut-off phenomenon for random reflections, Ann. Probab. 24(1996), 74-96. MR 97e:60012
  • 16. C. Radin, The pinwheel tilings of the plane, Annals of Math. 139(1994), 661-702. MR 95d:52021
  • 17. E. Rains, personal communication, 1995.
  • 18. J.S. Rosenthal, Random rotations: characters and random walks on $SO(n)$, Ann. Probab. 22(1994), 398-423. MR 95c:60008
  • 19. W.M. Schmidt, Diophantine Approximation. Lecture Notes in Math. No. 785, Springer-Verlag, 1980. MR 81j:10038
  • 20. N.J.A. Sloane, Encrypting by Random Rotations, in Cryptography, Lecture Notes in Computer Science, no. 149. T.Beth, editor. Berlin, 1983. MR 85i:94017
  • 21. F.E. Su, Methods for Quantifying Rates of Convergence for Random Walks on Groups, Ph.D. Thesis, Harvard University, 1995.

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

American Mathematical Society