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

  • 1. Daniel Asimov, The grand tour: a tool for viewing multidimensional data, SIAM J. Sci. Statist. Comput. 6 (1985), no. 1, 128–143. MR 773286, 10.1137/0906011
  • 2. Persi Diaconis, Group representations in probability and statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series, 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR 964069
  • 3. Persi Diaconis and Laurent Saloff-Coste, Comparison techniques for random walk on finite groups, Ann. Probab. 21 (1993), no. 4, 2131–2156. MR 1245303
  • 4. P. Erdös and P. Turán, On a problem in the theory of uniform distribution. I, Nederl. Akad. Wetensch., Proc. 51 (1948), 1146–1154 = Indagationes Math. 10, 370–378 (1948). MR 0027895
  • 5. B.M. Kloss, Limiting distributions on bicompact topological groups, Th. Probab. Appl. 4(1959), 237-270.
  • 6. A. Ya. Khinchin, Continued fractions, The University of Chicago Press, Chicago, Ill.-London, 1964. MR 0161833
  • 7. L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0419394
  • 8. Serge Lang, Introduction to Diophantine approximations, 2nd ed., Springer-Verlag, New York, 1995. MR 1348400
  • 9. W. J. Leveque, An inequality connected with Weyl’s criterion for uniform distribution, Proc. Sympos. Pure Math., Vol. VIII, Amer. Math. Soc., Providence, R.I., 1965, pp. 22–30. MR 0179150
  • 10. A. Lubotzky, R. Phillips, and P. Sarnak, Hecke operators and distributing points on the sphere. I, Comm. Pure Appl. Math. 39 (1986), no. S, suppl., S149–S186. Frontiers of the mathematical sciences: 1985 (New York, 1985). MR 861487, 10.1002/cpa.3160390710
  • 11. Jerrold E. Marsden, Elementary classical analysis, W. H. Freeman and Co., San Francisco, 1974. With the assistance of Michael Buchner, Amy Erickson, Adam Hausknecht, Dennis Heifetz, Janet Macrae and William Wilson, and with contributions by Paul Chernoff, István Fáry and Robert Gulliver. MR 0357693
  • 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 Walter Philipp, Berry-Esseen bounds and a theorem of Erdős and Turán on uniform distribution 𝑚𝑜𝑑1, Duke Math. J. 40 (1973), 633–649. MR 0337873
  • 15. Ursula Porod, The cut-off phenomenon for random reflections, Ann. Probab. 24 (1996), no. 1, 74–96. MR 1387627, 10.1214/aop/1042644708
  • 16. Charles Radin, The pinwheel tilings of the plane, Ann. of Math. (2) 139 (1994), no. 3, 661–702. MR 1283873, 10.2307/2118575
  • 17. E. Rains, personal communication, 1995.
  • 18. Jeffrey S. Rosenthal, Random rotations: characters and random walks on 𝑆𝑂(𝑁), Ann. Probab. 22 (1994), no. 1, 398–423. MR 1258882
  • 19. Wolfgang M. Schmidt, Diophantine approximation, Lecture Notes in Mathematics, vol. 785, Springer, Berlin, 1980. MR 568710
  • 20. N. J. A. Sloane, Encrypting by random rotations, Cryptography (Burg Feuerstein, 1982) Lecture Notes in Comput. Sci., vol. 149, Springer, Berlin, 1983, pp. 71–128. MR 707278, 10.1007/3-540-39466-4_6
  • 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
Email: su@math.hmc.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-98-02152-7
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